leetcode：84. 柱状图中最大的矩形面积_leetcode 84

题目来源

• leetcode：84. 柱状图中最大的矩形面积

题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {

    }
};
1
2
3
4
5
6

题目解析

题意

暴力求解1

两层循环，依次向后遍历，一边遍历一边记录最小的高度，计算面积，记录最大面积

遍历结束后，所有的单个柱子的面积以及组合柱子的面积全部计算了一遍，那么最大面积也得到了，算法的时间复杂度是$O(N^2)$

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int length = heights.size();
        int minHeight, maxArea = 0, width = 1;

        for (int i = 0; i < length; ++i) {
            // 单个柱子的面积
            maxArea = std::max(maxArea, heights[i] * 1);
            
            // 重置 高和宽
            minHeight = heights[i];
            width = 1;

            // 组合柱子的面积
            for (int j = i + 1; j < length; ++j) {
                minHeight = std::min(minHeight, heights[i]);
                ++width;
                
                maxArea = std::max(maxArea, minHeight * width);
            }
        }
        return maxArea;
    }
};
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

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        int ans = 0;
        // 枚举左边界
        for (int left = 0; left < n; ++left) {
            int minHeight = INT_MAX;
            // 枚举右边界
            for (int right = left; right < n; ++right) {
                // 确定高度
                minHeight = min(minHeight, heights[right]);
                // 计算面积
                ans = max(ans, (right - left + 1) * minHeight);
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

暴力求解2

很明显，暴力解法1存在大量的重复计算和没必要的计算，因为内层循环的第一次遍历结束后，所有的柱子都遍历一次了，也就是计算机知道了每个柱子的高度。

那么计算最大面积时，可以跳过一些情况，不进行计算。

我们可以枚举每一个柱子，寻找它的左右边界，计算面积并记录最大面积，那么那些不是柱子的左右边界的地方，并没有计算面积，虽然算法的时间复杂度仍然是O(n^2)，但相比于暴力求解法1，减少了大量的计算。

简单来说，就是枚举以每个矩形为高度的最大矩形的面积。

• 枚举必须以heights[0]为高度的最大矩形
• 枚举必须以heights[1]为高度的最大矩形
• …

具体来说就是：依次遍历柱形的高度，对每一个高度分别向两边扩散，求出以当前高度为矩形的最大宽度是多少。

为此，我们需要：

• 左边看一下，看最多能向左边延伸多长，找到大于等于当前柱形高度的最左边元素的下标；
• 右边看一下，看最多能向右延伸多长；找到大于等于当前柱形高度的最右边元素的下标。

对于每一个位置，我们都这样操作，得到一个矩形面积，求出它们的最大值。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int size = heights.size();
        int ans = 0;
        for (int mid = 0; mid < size; ++mid) {
            // 枚举高
            int height = heights[mid];
            int left = mid, right = mid;
            // 确定左右边界
            while (left - 1 >= 0 && heights[left - 1] >= height) {
                --left;
            }
            while (right + 1 >= 0 && heights[right + 1] >= height) {
                ++right;
            }
            // 计算面积
            ans = max(ans, (right - left + 1) * height);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复杂度分析：

超时，有没有方法可以一次遍历，不需要中心扩散就能够计算出每一个高度所对应的那个最大面积矩形的面积呢？

很容易想到的优化的思路就是「以空间换时间」。我们需要在遍历的过程中记录一些信息。

单调栈

记录什么信息呢？记录高度是不是可以呢？其实是不够的，因为计算矩形还需要计算宽度，很容易知道宽度是由下标确定的，记录了下标其实对应的高度就可以直接从输入数组中得出，因此，应该记录的是下标。

举个例子：[2, 1, 5, 6, 2, 3]

• 一开始看到的柱形高度为2，这个时候以这个2为高度的最大面积的矩形还不能确定，我们需要继续往右遍历，如下图：

• 然后看到高度为1的矩形，因为1比2小，所以2不能继续往右扩张了
  
• 这个时候2应该结算答案，我们计算一下必须以2为高度的最大矩形的面积，得到了2。因为下必须以2为高度的最大矩形的面积已经计算出来了，所以我们可以无视它了

• 继续往右遍历，看到了一个高度为5的矩形，5比1大，还是可以继续向右扩张的
  
• 接下来，遍历到高度为 6 的柱形，同样的，以柱形 1、5、6 为高度的最大矩形面积还是不能确定下来；

• 再接下来，遍历到高度为 2 的柱形。

• 此时，必须以高度为6的最大矩形的面积的宽度可以确定下来了，它就是夹在高度为 5 的柱形和高度为 2 的柱形之间的距离，它的高度是 6，宽度是 1。

• 将可以确定的柱形设置为虚线。
  
• 接下来柱形 5 对应的最大面积的矩形的宽度也可以确定下来，它是夹在高度为 1 和高度为 2 的两个柱形之间的距离；

• 确定好以后，我们将它标成虚线。

• 从上面可以发现：
  • 只要是遇到了当前柱形的高度比它上一个柱形的高度严格小的时候，一定可以确定它之前的某些柱形的最大宽度，并且确定的矩形宽度的顺序是从右边到左边
  • 这个现象告诉我们，在遍历的时候需要记录的信息就是遍历到的矩形的下标，它一左一右的两个矩形的下标的差就是这个面积最大的矩形对应的宽度
• 这个时候，还需要考虑的一个细节是，在确定一个矩形的面积的时候，除了右边要比当前严格小，其实还蕴含了一个条件，那就是左边也要比当前高度严格小
• 那如果是左边的高度和自己的相等怎么办？
  • 我们之前是只要比当前严格小，我们才可以确定一些柱形的最大宽度。大于或者等于之前看到的柱形的高度的时候，并不能确定
  • 因此我们确定当前柱形对应的宽度的左边界的时候，往回头看的时候，一定要找到第一个严格小于我们要确定的那个柱形的高度的下标。这个时候中间那些相等的矩形其实就可以当前不存在一样。因为它对应的最大矩形和它对应的最大矩形其实是一样的
• 因此：
  • 我们在遍历的时候，需要记录的是下标，如果当前的高度比它之前的高度严格小的时候，就可以直接确定之前的最大矩形的面积。
  • 为了确定这个最大矩形的左边界，我们还要找到第一个严格小于它的高度的矩形，向左回退的时候，其实就可以当中间这些柱形不存在一样。
• 这是因为我们就是想确定 6 的宽度，6 的宽度确定完了，其实我们就不需要它了，这个 5 的高度和这个 5 的高度确定完了，我们也不需要它了。
• 我们缓存数据的时候，是从左到右缓存的，我们计算出一个结果的顺序是从右到左的，并且计算完成之后我们就不再需要了，符合后进先出的特点，因此，我们可以用栈来作为缓存
• 当确定了一个柱形的高度的时候，我们就将它从栈顶移除，所有的柱形在栈中进栈一次，出栈一次，一开始栈为空，最后也一定要栈为空，表示这个高度数组里所有的元素都考虑完了
• 最后遍历到最后一个柱形，即高度为 3 的柱形。
  
• 一次遍历完成以后。接下来考虑栈里的元素全部出栈。也就是依次考虑还在栈里的柱形的高度。和刚才的方法一样，只不过这个时候右边没有比它高度还小的柱形了，这个时候计算宽度应该假设右边还有一个下标为len（这里等于 6） 的高度为 0 （或者 0.5，只要比 1 小）的柱形。

• 下标为 5 ，即高度为 3 的柱形，左边的下标是 4 ，右边的下标是 6 ，因此宽度是 6 - 4 - 1 = 1（两边都不算，只算中间的距离，所以减 1）；算完以后，将它标为虚线。

• 下标为 4 ，高度为 2 的柱形，左边的下标是 1 ，右边的下标是 6 ，因此宽度是 6 - 1 - 1 = 4；算完以后，将它标为虚线。

• 最后看下标为 1，高度为 1 的矩形，它的左边和右边其实都没有元素了，它就是整个柱形数组里高度最低的柱形，计算它的宽度，就是整个柱形数组的长度。
  
• 到此为止，所有的柱形高度对应的最大矩形的面积就都计算出来了。

这个算法经过一次遍历，在每一次计算最大宽度的时候，没有去遍历，而是使用了栈里存放的下标信息，以 O(1)O(1) 的时间复杂度计算最大宽度。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int size = heights.size();
        if(size == 0){
            return 0;
        }
        int maxArea = 0;
        std::stack<int> stack;
        for (int i = 0; i < size; ++i) {
            while (!stack.empty() && heights[i] <= heights[stack.top()]){
                int j = stack.top(); stack.pop();
                int k = stack.empty() ? -1 : stack.top();
                int currArea = (i - k - 1) * heights[j];
                maxArea = std::max(maxArea, currArea);
            }
            stack.push(i);
        }
        while (stack.empty()){
            int j = stack.top(); stack.pop();
            int k = stack.empty() ? -1 : stack.top();
            int currArea = (size - k - 1) * heights[j];
            maxArea = std::max(maxArea, currArea);
        }
        return maxArea;
    }
};
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

当然，也可以使用数组栈

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int size = heights.size();
        if(size == 0){
            return 0;
        }
        int maxArea = 0;
        std::vector<int> stack(size);
        int si = -1;
        for (int i = 0; i < size; ++i) {
            while (si != -1&& heights[i] <= heights[stack[si]]){
                int j = stack[si--];
                int k = si == -1 ? -1 : stack[si];
                int currArea = (i - k - 1) * heights[j];
                maxArea = std::max(maxArea, currArea);
            }
            stack[++si] = i;
        }
        while (si != -1){
            int j = stack[si--];
            int k = si == -1 ? -1 : stack[si];
            int currArea = (size - k - 1) * heights[j];
            maxArea = std::max(maxArea, currArea);
        }
        return maxArea;
    }
};
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

上面代码我们需要考虑两种特殊情况：

• 弹栈的时候，栈为空
• 遍历完成之后，栈中还有元素

为此我们可以在输入数组的两端加上两个高度为 0 （或者是 0.5，只要比 1 严格小都行）的柱形，可以回避上面这两种分类讨论。

这两个站在两边的柱形有一个很形象的名词，叫做哨兵（Sentinel）。 有了这两个矩形：

• 左边的柱形(第一个矩形)由于它一定比输入数组里的任何一个元素小，所以它肯定不会出栈，因此栈一定不会为空
• 右边的柱形(第二个矩形)由于它应比输入数组里任何一个元素小，它会让所有输入数组里的元素出栈(第一个哨兵元素除外)

这里栈对应高度，呈单调增加不减的形态，因此称为单调栈（Monotone Stack）。它是暴力解法的优化，计算每个柱形的高度对应的最大矩形的顺序由出栈顺序决定。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(heights.empty()){
            return 0;
        }

        heights.insert(heights.begin(), 0);
        heights.insert(heights.end(), 0);
        int size = heights.size();
        int maxArea = 0;
        std::stack<int> stack;
        stack.push(0);
        for (int i = 1; i < size; ++i) {
            while (heights[i] < heights[stack.top()]){
                int j = stack.top(); stack.pop();
                int k = stack.top();
                int currArea = (i - k - 1) * heights[j];
                maxArea = std::max(maxArea, currArea);
            }
            stack.push(i);
        }
        return maxArea;
    }
};
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

类似题目