柱状图中最大的矩形——单调栈的实践

待我称王封你为后i 2024-04-03 08:01 101阅读 0赞

#### 一、题目 ####

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

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

![0c49cbe705624ab69728bef6a990a56b.png][]

输入：heights = [2,1,5,6,2,3]
    输出：10
    解释：最大的矩形为图中红色区域，面积为 10

#### 二、枚举法 ####

我们需要在柱状图中找出最大的矩形，需要找到最左边第一个低于自己的矩形，和最右边第一个低于自己的矩形，因此我们可以考虑枚举矩形的宽和高，其中「宽」表示矩形贴着柱状图底边的宽度，「高」表示矩形在柱状图上的高度。

2.1 枚举宽

如果我们枚举「宽」，我们可以使用两重循环枚举矩形的左右边界以固定宽度 w，此时矩形的高度 h，就是所有包含在内的柱子的「最小高度」，对应的面积为 w×h

代码如下：

class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) { // 固定宽度
            int length = heights.size();
            int area = 0;
            for (int left = 0; left < length; left++) { // 枚举左边界
                int height = INT_MAX; // 一轮循环后，高度重新计算
                for (int right = left; right < length; right++) { // 枚举右边界
                    height = min(height, heights[right]); // 计算这一轮中最小的高度
                    area = max(area, (right - left + 1) * height); // 求面积
    
                }
            }
            return area;
        }
    };

2.2 枚举高

如果我们枚举「高」，我们可以使用一重循环枚举某一根柱子，将其固定为矩形的高度 h。随后我们从这跟柱子开始，分别向两侧延伸，直到遇到高度小于 h的柱子，就确定了矩形的左右边界。如果左右边界之间的宽度为 w，那么对应的面积为 w×h

class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) { // 固定高度
            int length = heights.size();
    
            int area = 0;
            for (int i = 0; i < length; i++) {
                int height = heights[i];
                int left = i;
                int right = i;
                while (((left - 1) >= 0) && (heights[left - 1] >= height)) { // 搜索左边界
                    left--;
                }
                while (((right + 1) < length) && (heights[right + 1] >= height)) { // 搜索右边界
                    right++;
                }
                area = max(area, (right - left + 1) * height);
            }
            return area;
        }
    };

可以发现，这两种暴力方法的时间复杂度均为 O(N2)O(N^2)O(N2)，会超出时间限制，我们必须要进行优化。考虑到枚举「宽」的方法使用了两重循环，本身就已经需要 O(N2)O(N^2)O(N2) 的时间复杂度，不容易优化，因此我们可以考虑优化只使用了一重循环的枚举「高」的方法。

#### 三、单调栈 ####

上一篇讲了，如果要查找左侧或者右侧第一个比自己大或者小的元素，就可以使用单调栈。

所以我们使用单调栈，先枚举左边的柱子，在枚举右边的柱子，最后计算面积：

class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
            int length = heights.size();
            vector<int> left(length);
            vector<int> right(length);
    
            stack<int> mono_stack; // 单调递增栈
    
            for (int i = 0; i < length; ++i) { // 寻找左边界
                while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                    mono_stack.pop();
                }
                left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
                mono_stack.push(i);
            }
    
            mono_stack = stack<int>();
            for (int i = length - 1; i >= 0; --i) { // 寻找右边界
                while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                    mono_stack.pop();
                }
                right[i] = (mono_stack.empty() ? length : mono_stack.top());
                mono_stack.push(i);
            }
    
            int ans = 0;
            for (int i = 0; i < length; ++i) { // 计算面积，(right -1) - (left + 1) +1
                ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
            }
            return ans;
        }
    };

优化

class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
            int n = heights.size();
            vector<int> left(n), right(n, n);
            
            stack<int> mono_stack;
            for (int i = 0; i < n; ++i) {
                while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                    right[mono_stack.top()] = i;
                    mono_stack.pop();
                }
                left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
                mono_stack.push(i);
            }
            
            int ans = 0;
            for (int i = 0; i < n; ++i) {
                ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
            }
            return ans;
        }
    };

参考：

[力扣][Link 1]

[0c49cbe705624ab69728bef6a990a56b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/970b0779a31446e4a177a3b49f2aeb5c.png
[Link 1]: https://leetcode.cn/submissions/detail/167110333/