84. 柱状图中最大的矩形

 1 class Solution 
 2 {
 3 public:
 4     int largestRectangleArea(vector<int>& heights) 
 5     {
 6         int n = heights.size();
 7         vector<int> left(n),right(n);
 8 
 9         //用单调栈在当前数左边 ——> 求比当前数小且最近的数
10         stack<int> stk;
11         for(int i = 0;i < n;i ++)
12         {
13             while(stk.size() && heights[stk.top()] >= heights[i]) stk.pop();
14 
15             if(stk.empty()) left[i] = -1;
16             else left[i] = stk.top();
17 
18             stk.push(i);
19         }
20 
21         //用单调栈在当前数右边 ——> 求比当前数小且最近的数
22         while(stk.size()) stk.pop();
23         for(int i = n - 1;i >= 0;i --)
24         {
25             while(stk.size() && heights[stk.top()] >= heights[i]) stk.pop();
26 
27             if(stk.empty()) right[i] = n;
28             else right[i] = stk.top();
29 
30             stk.push(i);
31         }
32         int res = 0;
33         for(int i = 0;i < n;i ++) res = max(res,heights[i] * (right[i] - left[i] - 1));
34 
35         return res;
36     }
37 };