Create 084.Largest-Rectangle-in-Histogram_v1.cpp

wisdompeak · web-flow · commit a2c45e9b28f2 · 2022-07-09T16:12:59.000-07:00
diff --git a/Stack/084.Largest-Rectangle-in-Histogram/084.Largest-Rectangle-in-Histogram_v1.cpp b/Stack/084.Largest-Rectangle-in-Histogram/084.Largest-Rectangle-in-Histogram_v1.cpp
@@ -0,0 +1,37 @@
+class Solution {
+public:
+    int largestRectangleArea(vector<int>& heights) 
+    {
+        int n = heights.size();        
+        stack<int>stk;        
+        vector<int>nextSmaller(n, n);
+        for (int i=0; i<heights.size(); i++)
+        {
+            while (!stk.empty() && heights[stk.top()] > heights[i])
+            {
+                nextSmaller[stk.top()] = i;
+                stk.pop();
+            }
+            stk.push(i);                
+        }
+        
+        while (!stk.empty()) stk.pop();
+        vector<int>prevSmaller(n, -1);
+        for (int i=0; i<heights.size(); i++)
+        {
+            while (!stk.empty() && heights[stk.top()] > heights[i])
+            {                                
+                stk.pop();
+            }
+            if (!stk.empty())
+                prevSmaller[i] = stk.top();
+            stk.push(i);              
+        }
+                
+        int ret = 0;
+        for (int i=0; i<n; i++)
+            ret = max(ret, heights[i]*(nextSmaller[i] - prevSmaller[i] - 1));
+        
+        return ret;          
+    }
+};
