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

糖逗

题目描述：

给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

 

示例 1:



输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：



输入： heights = [2,4]
输出： 4
 

提示：

1 <= heights.length <=105
0 <= heights[i] <= 104

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/0ynMMM
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int res = 0;
        stack<int> store;
        store.push(-1);
        for(int i = 0; i < heights.size(); i++){
            while(store.size() > 1 && heights[store.top()] > heights[i]){
                int height = heights[store.top()];
                store.pop();
                int width = i - store.top() - 1;
                res = max(res, height * width);
            }
            store.push(i);
        }
        while(store.size() > 1){
            int height = heights[store.top()];
            store.pop();    
            int width = heights.size() - store.top() - 1;
            res = max(res, height * width);

        }
        return res;
    }
};

hornwong

Azhbdhlxt

6