柱状图中最大的矩形

题目描述

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

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

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10

题解：

方法一：暴力求解，对当前高度，进行向左和向右进行遍历直到遇到其高度比当前高度小的停止，然后计算宽度，最后计算面积更新结果。
方法二：用栈来存储heights的下标，当遇到高度比栈顶对应的高度小时，则停下来，循环弹出栈顶获取高度h，然后当下一个栈顶等于h时，也弹出，然后正常统计其宽度=i-s.top-1，如果栈为空，则宽度为i，然后计算面积更新结果。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();

        //处理个数为0和1的情况
        if(n<=0)
            return 0;
        else if(n==1)
            return heights[0];

        int res = 0;
        //用栈保存heights的下标
        stack<int> s;

        int i;
        for(i=0;i<n;i++)
        {
            //当前遍历的高度比栈顶下标对应的高度小时，就可以确定之前的矩形的面积
            while(!s.empty()&&heights[i]<heights[s.top()])
            {
                //栈顶对应的高度
                int h = heights[s.top()];
                //当下一个栈顶与h一样则直接弹出
                while(!s.empty()&&heights[s.top()]==h)
                    s.pop();

                //计算宽度，当栈为空说明，高度为h的矩形其宽度为i
                //当栈不为空，那么宽度为i-s.top()-1
                int w;
                if(s.empty())
                    w = i;
                else
                    w = i-s.top()-1;

                //更新结果
                res = max(res,h*w);    
            }
            s.push(i);
        }

         //当栈不为空, 继续计算相应的矩形面积, 此时i==n
        while(!s.empty())
        {
            int h = heights[s.top()];
            while(!s.empty()&&heights[s.top()]==h)
                s.pop();

            int w;
            if(s.empty())
                w = i;
            else
                w = i-s.top()-1;

            res = max(res,h*w);    
        }

        return res;
    }
};