leetcode84.柱状图中最大矩形

Posted on | In |
Words count in article: 456 | Reading time ≈ 2

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

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

示例：

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

分析：

1
要求最大矩形的面积，考虑当前位置i所构成的最大矩形，只需要考虑前后最接近它且高度小于它的位置，显然，只需要维护两个单调栈即可

代码

  • C++

  • 借助STL
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>& h) {
        int n = h.size();
        stack<int> stk;
        vector<int> left(n), right(n);

        for (int i = 0;i < n;i ++) {
            while (!stk.empty() && h[stk.top()] >= h[i]) stk.pop();
            if (stk.empty()) left[i] = -1;
            else left[i] = stk.top();
            stk.push(i);
        }

        stk = stack<int>();
        for (int j = n - 1;j >= 0;j --) {
            while (!stk.empty() && h[stk.top()] >= h[j]) stk.pop();
            if (stk.empty()) right[j] = n;
            else right[j] = stk.top();
            stk.push(j);
        }

        int res = 0;
        for (int i = 0;i < n;i ++)
            res = max(res, h[i] * (right[i] - left[i] - 1));

        return res;
    }
};
  • 数组模拟
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
30
31
32
const int N = 100010;

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int res = 0;
        int n = heights.size();
        int l[N], r[N], q[N];
        int tt = 0;
        q[0] = 0;
        heights.insert(heights.begin(), -1);
        heights.push_back(-1);
        for (int i = 1;i <= n;i ++) {
            while (heights[i] <= heights[q[tt]]) tt --;
            l[i] = q[tt];
            q[++ tt] = i;
        }

        tt = 0;
        q[0] = n + 1;
        for (int i = n;i >= 1;i --) {
            while (heights[i] <= heights[q[tt]]) tt --;
            r[i] = q[tt];
            q[++ tt] = i;
        }

        for (int i = 1;i <= n;i ++) 
            res = max(res, (r[i] - l[i] - 1) * heights[i]);

        return res;
    }
};

[原题链接](84. 柱状图中最大的矩形 - 力扣（Leetcode）)

[相似题目](2357. 使数组中所有元素都等于零 - 力扣（Leetcode）)

0%