C++刷leetcode（84. 柱状图中最大的矩形）【单调递增栈】

糖逗

题目描述：

1. 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
   
2. 
   
3. 求在该柱状图中，能够勾勒出来的矩形的最大面积。
   
4. 
   
5.  
   
6. 
   
7. 
   
8. 
   
9. 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
   
10. 
    
11.  
    
12. 
    
13. 
    
14. 
    
15. 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
    
16. 
    
17.  
    
18. 
    
19. 示例:
    
20. 
    
21. 输入: [2,1,5,6,2,3]
    
22. 输出: 10
    
23. 
    
24. 来源：力扣（LeetCode）
    
25. 链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
    
26. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. int largestRectangleArea(vector<int>& heights) {
   
2.         int ans = 0;
   
3.         stack<int> temp;
   
4.         heights.insert(heights.begin(), 0);//因为right = i-1为了防止越界
   
5.         heights.push_back(0);
   
6.         for (int i = 0; i < heights.size(); i++)
   
7.         {
   
8.             while (!temp.empty() && heights[temp.top()] > heights[i])
   
9.             {
   
10.                 int cur = temp.top();
    
11.                 temp.pop();
    
12.                 int left = temp.top() + 1;
    
13.                 int right = i - 1;
    
14.                 ans = max(ans, (right - left + 1) * heights[cur]);
    
15.             }
    
16.             temp.push(i);
    
17. 
    
18.         }
    
19.         return ans;
    
20.         
    
21.     }

复制代码