【LeetCode 84】柱状图中最大的矩形

题目链接

【题解】

维护一个单调递增的栈。
会发现栈内的第i个元素的前面一个(i-1)元素在原始的序列中的数字
都是要高于第i个元素的。(或者没有元素)
那么第i个元素往左最多可以扩展到第i-1个元素的右边。
那么它的右边界在哪里呢?当然是一直延伸到栈顶元素所在的位置了。
此时如果新加来的元素x一直会小于sta[i]
也即sta[i]只能延伸到i-1那个位置了(原来的栈顶)
这时候就能用sta[i]来更新答案了。即 x元素所在位置-1-第i个元素前面一个元素所在的位置。再乘上第i个元素的高度。

【代码】

class Solution {

public:

    int largestRectangleArea(vector<int>& heights) {

        if (heights.empty()) return 0;

        int sta[100000];memset(sta,0,sizeof(sta));

        int top = 0;

        sta[++top] =-1;

        int ma = 0;

        for (int i = 0;i<(int)heights.size();i++){

            if (top==1 || heights[i]>=heights[sta[top]]){

                sta[++top] = i;

            }else{

                while (top>1 && heights[i]<heights[sta[top]]){

                   ma = max(ma,(i-1-sta[top-1])*heights[sta[top]]) ;

                   top--;

                }

                sta[++top] = i;

            }

            /*

            for(int j = 1;j<=top;j++)

            {

                cout<<sta[j]<<" ";

            }

            cout<<endl;*/

        }

        while (top>1){

            ma = max(ma,((int)heights.size()-1-sta[top-1])*heights[sta[top]]);

            top--;

        }

        return ma;

    }

};