直方图内最大矩形

题意

给定一个形如直方图的矩形列，求其中最大的矩形的面积

方法

枚举底(TLE)

分析

如果我们选定了长方形的底，那么这区间里最小的高就是我们要用的高度。

这样能得到，所选的底对应的最大面积

变成伪代码就是

for i = 1 -> heights.length
	for j = i -> heights.length
		ans = max(ans,(j-i) * min(heights[i..j]))

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型vector 
     * @return int整型
     */
    int largestRectangleArea(vector<int>& heights) {
        int ans = 0;
        for(int i=0;i<heights.size();i++){ // 左侧
            int m = heights[i]; // 当前底对应的最大可选高
            for(int j=i;j<heights.size();j++){ // 右侧
                m = min(m,heights[j]);
                ans = max(ans,m * (j-i+1)); // 面积
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度: 先选左侧点，再选右侧点，所以总时间复杂度为$O(n^2)O(n^2)$

空间复杂度: 只用了常数个额外变量，所以空间复杂度为$O(1)O(1)$

单调栈

分析

选取的矩形一定高等于存在的某个矩形的高

那么一个高如果被选择，最好的时机，就是这个矩形之前最后一个比它小的矩形作为开始，之后首个比它小的矩形作为结束

那么如果有办法维护数据，方便找到这两个位置就能相减得到长度

注意到，如果数据上有$AA$在$BB$之前,而$A>BA>B$,那么对于B以后的数来说，$AA$的具体值没有任何意义，它一旦大于$BB$,那么最多高度只能选到$BB$

所以维护一个下标从小到大，值也从小到大的数组，一旦出现上述情况，去掉$AA$

那么回到了我们上面分析的结果：去掉$AA$时就是选$AA$作为结束位置的最好时机，而起始位置，就是维护的数组中$AA$的前一个的值

因此常数时间能得到选$AA$作为高时对应的矩形长度

样例

以题目样例数据[3,4,7,8,1,2]为例

所以最后输出14即可

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型vector 
     * @return int整型
     */
    int largestRectangleArea(vector<int>& heights) {
        int ans = 0;
        vector<int> r;
        heights.push_back(0); // 减少if 方便计算
        for(int i = 0;i<heights.size();i++){
            // 当前比前面的小
            while(r.size() && heights[i] <= heights[r.back()]){
                int h = heights[r.back()];
                r.pop_back();
                ans = max(ans, (i - 1  - (r.size()?r.back():-1)) * h); // 面积
            }
            r.push_back(i);
        }
        return ans;
    }
};

复杂度分析

时间复杂度: 计算每个高对应的宽为常数代价，所以时间复杂度为$O(n)O(n)$

空间复杂度: 用来记录的辅助单调栈不超过原数组长度，所以空间复杂度为$O(n)O(n)$