C++刷leetcode（剑指 Offer II 039. 直方图最大矩形面积）【递增栈】

糖逗

题目描述：

1. 给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
   
2. 
   
3. 求在该柱状图中，能够勾勒出来的矩形的最大面积。
   
4. 
   
5.  
   
6. 
   
7. 示例 1:
   
8. 
   
9. 
   
10. 
    
11. 输入：heights = [2,1,5,6,2,3]
    
12. 输出：10
    
13. 解释：最大的矩形为图中红色区域，面积为 10
    
14. 示例 2：
    
15. 
    
16. 
    
17. 
    
18. 输入： heights = [2,4]
    
19. 输出： 4
    
20.  
    
21. 
    
22. 提示：
    
23. 
    
24. 1 <= heights.length <=105
    
25. 0 <= heights[i] <= 104
    
26. 
    
27. 来源：力扣（LeetCode）
    
28. 链接：https://leetcode.cn/problems/0ynMMM
    
29. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int largestRectangleArea(vector<int>& heights) {
   
4.         int res = 0;
   
5.         stack<int> store;
   
6.         store.push(-1);
   
7.         for(int i = 0; i < heights.size(); i++){
   
8.             while(store.size() > 1 && heights[store.top()] > heights[i]){
   
9.                 int height = heights[store.top()];
   
10.                 store.pop();
    
11.                 int width = i - store.top() - 1;
    
12.                 res = max(res, height * width);
    
13.             }
    
14.             store.push(i);
    
15.         }
    
16.         while(store.size() > 1){
    
17.             int height = heights[store.top()];
    
18.             store.pop();   
    
19.             int width = heights.size() - store.top() - 1;
    
20.             res = max(res, height * width);
    
21. 
    
22.         }
    
23.         return res;
    
24.     }
    
25. };

复制代码

hornwong

Azhbdhlxt

6