Sitch's Blog
0%

LeetCode-No-84

发表于 分类于 Valine：

最大矩形

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

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

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

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

 

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

题目分析

  1. 想要知道最大矩形，肯定先要知道每根柱子怎么形成矩形的

  2. 对柱子 i，高度为 hi，以i为中心往两边扩展，只要碰到的柱子高度 Hj=hi，那么形成的矩形必然是以 hi 为高构造。

  3. 假如 Hj<hi，那么这个矩形的高就是新的 Hj，而这个 Hj 构造的矩形必然会出现在以柱子 j 为中心扩展的时候，所以不必考虑降低现在的高度。

  4. 所以对柱子 i 的扩展，往左右两边找，碰到矮的停下来，确定两边边界，边界高度 Hj=hi，这个即是这个 i 自己能做出来的最大矩形。 可以双重循环扫描，但不是重点，这里学习题解大神的栈思路。 # 题解分析：栈保留边界

  5. 首先有一层主循环遍历所有柱子，从左到右，当前柱子为 i。

  6. 我们目的是要找i的两个边界，因为是从左到右扫描，即我们可以顺手找到 i 的右边界。只要扫描时碰到比 i 矮的就知道这个是右边界了。

  7. 但是碰到比 i 高或者相等的柱子 j 怎么办呢？j 不会是 i 的边界 ，但我们也要找 j 的边界。因此我们要把未处理的 i 和 j 都留下来。

  8. 而继续往后找的时候， i 的右边界x 必然是 j 的右边界或者之外 （hi<=hj) 。 因此对于下一个柱子 x： 4.1 假如我们先判断 x 是不是 i 的边界，假如它是，它也不一定就是 j 的右边界 ，我们还得用 x 和 j 比较一次。假如它不是，它也不一定就不是 j 的右边界，还是得 x j 比较一次，所以先判定 i 的边界很鸡肋。 4.2 假如先判断 x 是不是更高的 j 的右边界，假如它不是，那么肯定也不是 i 的边界，假如它是，那么可以继续判定是不是更矮的 i 的右边界。

  9. 因此，我们的扫描过程是这样的，从左到右，且保留的柱子高度递增（因为只要更高的才会保留，否则是作为右边界判定）。 且判定的顺序是高的在前，低的在后，即新的在前，旧的在后，因此保留柱子的数据结构是：栈。 因此遇到一个新柱子，与栈顶比较，更高则继续压栈。更低则是栈顶的右边界，然后栈顶出栈，判定是不是下一个栈顶的右边界。

  10. 右边界解决了，我们还需要确定每个柱子 i 的左边界，左边界肯定在左边 ， 并且左边界也要比 i 矮，而我们的栈又是高度递增的= =+显然，我们可以利用出栈过程。 在栈顶确定了右边界，然后出栈的时候： 6.1 下面的那个柱子高度大于【栈顶右边界高度Hr】，那么这个柱子不是左边界，而可以组成这个矩形（因为有右边界后，矩形最低高度是Hr，只要高于Hr，都是）我们继续出栈寻找即可。 6.2 即一直出栈，直到出了个高度小于等于【栈顶右边界高度Hr】的柱子 x ，那么 x 就是上面这个矩形的左边界。 出栈到边界了怎么办？在数组开头预备一个0作为栈底标志位结束出栈。 同样压栈到边界了怎么办？在数组结尾预备一个0作为启动出栈的标志位。

  11. 此时 i 的左右边界都能找到，高度为 i ，计算面积。

总之精髓在于出栈过程，从栈顶的右边界，一直出栈到满足的左边界，中间这些柱子形成当前最大矩形。

题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int largestRectangleArea(vector<int& heights) 
    {
        //题解学习
        std::stack<int Lefts;
        heights.insert(heights.begin(),0);//补0作为边界判断
        heights.insert(heights.end(),0);
        int result=0;
        int temp;
        for(int i=0;i<heights.size();i++)
        {   
            //栈单调递增，当碰到一个i 比栈顶矮，则它必是栈顶的右边界
            //再逐渐出栈，每次出栈循环，都是栈顶作为中心，而栈单调递增，栈顶下面一个更矮的必是栈顶的左边界，左右边界确定，则栈顶位置能形成的矩阵面积可计算完毕。
            //直到栈顶比 i 还矮，那 i 就不能作为右边界了 ，栈顶此时的右边界也找不到，则 i 入栈待命当左边界，然后for下一轮
            while(Lefts.empty()!=true && heights[Lefts.top()]heights[i])//找到比栈顶矮的柱子，即栈顶柱子的右边界
            {     
                temp=Lefts.top();
                Lefts.pop();
                result = max(result, (i - Lefts.top()-1)*heights[temp]);
            }
            Lefts.push(i);
        }

        return result;


    }
};