Update 907.Sum-of-Subarray-Minimums.cpp

wisdompeak · web-flow · commit acfbfe38e7eb · 2021-05-09T21:49:27.000-07:00
diff --git a/Stack/907.Sum-of-Subarray-Minimums/907.Sum-of-Subarray-Minimums.cpp b/Stack/907.Sum-of-Subarray-Minimums/907.Sum-of-Subarray-Minimums.cpp
@@ -1,46 +1,40 @@
 class Solution {
 public:
-    int sumSubarrayMins(vector<int>& A) 
+    int sumSubarrayMins(vector<int>& arr) 
     {
-        int n = A.size();
-        vector<int>prevSmaller(n);
-        vector<int>nextSmaller(n);
-        for (int i=0; i<n; i++)
-        {
-            prevSmaller[i] = -1;
-            nextSmaller[i] = n;
-        }
-        
+        int n = arr.size();        
+        vector<int>nextSmaller(n, n);        
+        vector<int>prevSmaller(n, -1);
+
         stack<int>Stack;
         for (int i=0; i<n; i++)
         {
-            while (!Stack.empty() && A[Stack.top()] > A[i])
+            while (!Stack.empty() && arr[Stack.top()]>arr[i])
             {
                 nextSmaller[Stack.top()] = i;
                 Stack.pop();
             }
-            Stack.push(i);
+            Stack.push(i);                    
         }
-        
+                
         while (!Stack.empty()) Stack.pop();
-        for (int i=0; i<n; i++)
+        for (int i=n-1; i>=0; i--)
         {
-            while (!Stack.empty() && A[Stack.top()] > A[i])
-                    Stack.pop();
-            
-            if (!Stack.empty()) prevSmaller[i] = Stack.top();
-                Stack.push(i);
+            while (!Stack.empty() && arr[Stack.top()]>=arr[i])
+            {
+                prevSmaller[Stack.top()] = i;
+                Stack.pop();
+            }
+            Stack.push(i); 
         }
-                
-        long result = 0;
+
+        long ret = 0;
         long M = 1e9+7;
         for (int i=0; i<n; i++)
         {
-            long times = (i - prevSmaller[i])*(nextSmaller[i] - i);
-            result += A[i]*times;
-            result = result%M;
+            long count = (i-prevSmaller[i])*(nextSmaller[i]-i) % M;
+            ret = (ret+arr[i]*count) %M;
         }
-        
-        return result;        
+        return ret;
     }
 };
