# 84

Apr 5th, 2021
73
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Solution {
2. public:
3.     int largestRectangleArea(vector<int>& heights) {
4.         int sz = heights.size(), ans=0, p;
5.         vector<int> leftMin(sz), rightMin(sz);
6.
7.         //Find left min and right max for each index.
8.         leftMin[0] = -1;
9.         rightMin[sz-1] = sz;
10.         for(int i=1; i<sz; i++){
11.             p = i-1;
12.             while(p >= 0 && heights[p] >= heights[i])
13.                 p = leftMin[p];
14.             leftMin[i] = p;
15.         }
16.         for(int i=sz-2; i>=0; i--){
17.             p = i+1;
18.             while(p < sz && heights[p] >= heights[i])
19.                 p = rightMin[p];
20.             rightMin[i] = p;
21.         }
22.
23.         // For each index's height, calculate the rectangle formed with that height.
24.         for(int i=0; i<sz; i++)
25.             ans = max(ans, heights[i]*(rightMin[i]-leftMin[i]-1));
26.
27.         return ans;
28.     }
29. };
RAW Paste Data