题意理解

一个直方图可以视为多个宽度为1的矩形的紧密相连，每个矩形的高为heights数组中对应的值。这些矩形覆盖了平面上的一个区域，我们要在其中找到一个面积最大的矩形。

方法一

暴力搜索
面积最大的矩形的高一定是heights中的某个值，否则矩形可以增高，从而面积扩大。我们遍历每一个高度，对于heights[i]，分别向左向右搜索。如果遇到了某个高度小于heights[i]，说明以heights[i]为高的矩形的宽度不能再增加了，即到达了左右边界，此时可以得到对应矩形的面积，并更新当前最大面积。

以一个heights[i]为例，其寻找左右边界（即矩形宽度）的过程如图所示：

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型vector 
     * @return int整型
     */
    int largestRectangleArea(vector<int>& heights) {
        // write code here
        int maxm = 0;
        for (int i=0;i<heights.size();i++)
        {
            //找到左右的边界
            int left=i, right=i;
            while(left>=0 && heights[left]>=heights[i]) left--;
            while(right<heights.size() && heights[right]>=heights[i]) right++;
            //计算当前面积并更新最大值
            int area = heights[i] * (right - left -1);
            if (area > maxm) maxm = area;
        }
        return maxm;
    }
};

时间复杂度： $O(N^2)O(N^2)$。外部循环遍历heights数组，内部循环寻找左右边界最坏的情况遍历了整个heights数组。
空间复杂度： $O(1)O(1)$。没有开辟新的空间。

方法二

单调栈
对于每个高度heights[i]，如何查询其左右边界是可以优化的地方。我们从左向右遍历heights，当heights[i-1]小于heights[i]的时候，以heights[i]为高的矩形不能向左扩展，所以此时可以不用操作。至于右边界在哪里，我们先不考虑，继续向右遍历heights，当出现heights[i-1]大于等于heights[i]的时候，说明位置i前面的高度的右边界找到了，依次求出它们对应最大矩形的面积。

我们使用单调栈实现这一过程：
从左向右遍历heights；

1. 栈为空或者heights[i]大于栈顶元素，把heights[i]入栈；
2. heights[i]小于等于栈顶元素，弹出栈顶元素，计算以其为高的最大矩形的面积（只能向右侧扩展，因此可以通过累计的方法计算宽度），并更新输出值。这里使用left数组记录每个heights[i]左侧有几个相邻且高于它的矩形。这样的原因是，当弹出栈顶元素后，栈内元素是递增的，但是实际直方图中栈内的两个相邻元素间可能有比他们都高的矩形。重复弹出操作，直到满足条件1，把heights[i]入栈。

遍历完毕后，若栈非空，不断从栈顶弹出元素，计算以它为高的最大矩形面积，并更新最大值。

下图以[3,4,7,8,1,2]为例，列出了left数组和栈内元素的变化情况，以及每扫描一个heights[i]之后maxm的值：

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型vector 
     * @return int整型
     */
    int largestRectangleArea(vector<int>& heights) {
        // write code here
        int maxm = 0;
        stack<pair<int,int>> s;
        //left记录对应的heights[i]的左侧有多少相邻的矩形不低于它，不包含其本身。
        vector<int> left;
        for (int i=0;i<heights.size();i++) left.push_back(0);
        for (int i=0;i<heights.size();i++)
        {
            if (s.empty() || s.top().first<heights[i])
            {
                s.push(make_pair(heights[i], 0));
            }
            else if (s.top().first>=heights[i])
            {
                //right表示当前高度右侧有多少相邻的矩形高于它，包含其本身
                int right = 1;
                while (!s.empty() && s.top().first>=heights[i])
                {
                    left[i] = left[i] + s.top().second + 1;
                    maxm = max(maxm, s.top().first*(right+s.top().second));
                    right = right + s.top().second + 1;
                    s.pop();
                }
                s.push(make_pair(heights[i], left[i]));
            }
        }
        int right = 1;
        while (!s.empty())
        {
            maxm = max(maxm, s.top().first*(right+s.top().second));
            right = right + s.top().second + 1;
            s.pop();
        }
        return maxm;
    }
};

时间复杂度： $O(N)O(N)$。扫描了一遍heights数组，尽管内部还有一个while循环，但每个heights[i]只会入栈出栈一次。
空间复杂度： $O(N)O(N)$。使用了left数组，长度和heights对应；同时栈s在最坏情况下的长度也为N。