LeetCode-084-栈-单调栈

剑指 Offer II 039. 直方图最大矩形面积

class Solution {
public:
    int largestRectangleArea(vector& heights) {
        //单调递增栈
        stack s;//s中保存的是直方图的索引
        s.push(-1);//-1相当于一个sentinel
        int maxArea = 0;
        for (int i = 0; i < heights.size(); ++i) 
        {
            //若当前柱高<=栈顶柱高，将栈顶柱子出栈，并计算栈顶柱子为顶的最高矩阵面积，直至可入栈
            //出栈的目的是在“栈顶->栈底”的方向上找到第一个“高度小于当前柱子的高度”元素，这样，被找到的这个元素和当前元素之间(不含这两个边界元素)夹着的矩形可勾勒出最大面积的矩形
            while (s.top() != -1 && heights[s.top()] >= heights[i]) 
            {
                int height = heights[s.top()];
                s.pop();
                int width = i - s.top() - 1;
                maxArea = max(maxArea, height * width);
            }
            //若当前柱高>栈顶柱高，那么该柱子下标入栈
            s.push(i);
        }
        //[1,2,3,4,5]如果按照这个顺序入栈，在上面的过程中是没有机会进行入栈的操作，所以这里还要进行计算一次
        while (s.top() != -1) 
        {
            int height = heights[s.top()];
            s.pop();
            int width = heights.size() - s.top() - 1;
            maxArea = max(maxArea, height * width);
        }
        return maxArea;        
    }
};