跳转至

84 柱状图最大的矩形

https://leetcode.cn/problems/largest-rectangle-in-histogram/description/

解法一: 暴力枚举

枚举宽:枚举左边界,再枚举右边界

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int ans = 0;
        int n = heights.size();
        for(int i = 0; i < n; i++){
            int minHeight = heights[i];
            for(int j = i; j < n; j++){
                minHeight = min(minHeight, heights[j]);
                ans = max(ans, (j - i + 1) * minHeight);
            }
        }
        return ans;
    }
};

枚举高:

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int ans = 0;
        int n = heights.size();
        // 枚举每根柱子的高度
        for(int mid = 0; mid < n; mid++){
            int height = heights[mid];
            int left = mid, right = mid;
            // 如果左右柱子比当前枚举的柱子高,那么矩形的高度仍然为当前枚举柱子的高度heights[mid]
            while(left - 1 >= 0 && heights[left - 1] >= height) --left;
            while(right + 1 < n && heights[right + 1] >= height) ++right;
            // 注意这里left和right都指向最后一个比枚举柱子高度大的柱子
            // 与单调栈做法不同,这里为right - left + 1(单调栈是right - left - 1)
            ans = max(ans, (right - left + 1) * height);
        }
        return ans;
    }
};

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

解法二: 单调栈

朴素版

单调栈常用于查找比它大的第一个数 or 比它小的第一个数

单调递增栈:栈内离栈顶越近(下标越大),栈元素越大;栈顶元素为栈内最大

  • 当有新元素进入,如果新元素比栈顶元素大,直接入栈。
  • 当有新元素进入,如果新元素比栈顶元素小,栈弹出,直到满足新元素比栈顶元素大,再将新元素入栈。

由此可见,新元素C使栈顶元素A弹出后,下一个栈顶元素B是A左边第一个比B小的元素,新元素C是A右边第一个比C小的元素

由暴力枚举高的解法可知道,我们枚举高度后需要分别往两边寻找比它矮的第一个柱子(数),因此可以使用单调栈

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int ans = 0;
        int n = heights.size();
        vector<int> left(n), right(n);
        stack<int> stk;
        for(int i = 0; i < n; i++){
            while(!stk.empty() && heights[stk.top()] >= heights[i]) stk.pop();
            left[i] = (stk.empty() ? -1 : stk.top());
            stk.push(i);
        }
        stk = stack<int>();
        for(int i = n - 1; i >= 0; i--){
            while(!stk.empty() && heights[stk.top()] >= heights[i]) stk.pop();
            right[i] = (stk.empty() ? n : stk.top());
            stk.push(i);
        }
        for(int i = 0; i < n; i++){
            // right 和 left 都指向第一个比枚举柱子小的柱子,因此不包含left 和 right
            // 宽度计算为: (right - 1) - (left + 1) + 1 = right - left - 1
            ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度:O(N)。
  • 空间复杂度:O(N)。

每一个位置只会入栈一次(在枚举到它时),并且最多出栈一次。

因此当我们从左向右/总右向左遍历数组时,对栈的操作的次数就为 O(N)。所以单调栈的总时间复杂度为 O(N)。

优化版

对上述进行优化

新元素C使栈顶元素A弹出后,下一个栈顶元素B是A左边第一个比B小的元素,新元素C是A右边第一个比C小的元素

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int len = heights.size() + 2;
        vector<int> height(len);
        // 在heights数组基础上在头尾加上0元素
        // 这是因为以heights[0](heights[heights.size() - 1])作为柱子高度时,缺少左边界(右边界)
        // 为其补上左右边界,使其能够计算heights[0](heights[heights.size() - 1])作为柱子高度时的面积
        height[0] = 0;
        height[len - 1] = 0;
        for(int i = 1; i < len - 1; i++)
            height[i] = heights[i - 1];
        stack<int> stk;
        int ans = 0;
        for(int i = 0; i < len; i++){
            while(!stk.empty() && height[i] < height[stk.top()]){
                // 新元素i让栈弹出,栈顶元素为stk.top()
                int idx = stk.top();
                stk.pop();
                // 这里的stk.top()为弹出后的下一个栈顶元素
                int w = i - stk.top() - 1;
                // 高度为最初的栈顶元素
                ans = max(ans, w * height[idx]);
            }
            // 没有弹出时不需要计算面积
            stk.push(i);
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度:O(N)。
  • 空间复杂度:O(N)。