题目描述

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

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

示例

示例1:

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

示例2:

1
2
输入： heights = [2,4]
输出： 4

提示:

1
2
3
1 <= heights.length <=105

0 <= heights[i] <= 104

代码

暴力解法:

这种解法简单，但是效率低，不通过。

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int max = heights[0];
        int len = heights.size();
        for (int i = 0; i < len; ++i) {
            for (int j = i; j < len; ++j) {
                int tmp = getValue(heights, i, j);
                max = tmp > max ? tmp : max;
            }
        }
        return max;
    }
    int getValue(vector<int>& heights, int i, int j) {
        int min = heights[i];
        int ti = i;
        while (i < j) {
            ++i;
            min = heights[i] < min ? heights[i] : min;
        }
        // return i == 0 ? (min * (j-i+1)) : min * (j-i);
        return min * (j-ti+1);
    }
};

从一根柱向左右蔓延

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int max = heights[0];
        for (int i = 0; i < heights.size(); ++i) {
            int tmp = getHeight(heights, i, heights.size());
            max = tmp > max ? tmp : max;
        }
        return max;
    }
    int getHeight(vector<int>& heights, int i, int len) {
        int tmpi, tmpj;
        tmpi = tmpj = i;
        while (tmpi > 0 && heights[tmpi-1] >= heights[i]) {
            --tmpi;
        }
        while (tmpj < len-1 && heights[tmpj+1] >= heights[i]) {
            ++tmpj;
        }
        return heights[i] * (tmpj-tmpi+1);
    }
};

单调栈

效率比暴力解高很多，两次遍历，可以优化成一次遍历。

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) {
        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);
        }
        int max = 0;
        for (int i = 0; i < n; ++i) {
            int tmp = (right[i] - left[i] - 1) * heights[i];
            max = tmp > max ? tmp : max;
        }
        return max;
    }
};

单调栈 + 常数优化

很妙的解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n), right(n, n); // 注意这里哨兵为 n
        stack<int> stk;
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && heights[stk.top()] >= heights[i]) {
                right[stk.top()] = i;
                stk.pop();
            }
            left[i] = (stk.empty() ? -1 : stk.top());
            stk.push(i);
        }
        int max = 0;
        for (int i = 0; i < n; ++i) {
            int tmp = (right[i] - left[i] - 1) * heights[i];
            max = tmp > max ? tmp : max;
        }
        return max;
    }
};

题目来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/largest-rectangle-in-histogram