柱形图中最大的矩形

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

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

示例 1:

img

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

示例 2：

img

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

提示：

  • 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        //因为要求的是小于，所以是大压小
        int[] stack = new int[n];
        int top = -1;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            while (top != -1 && heights[i] < heights[stack[top]]) {
                int left;
                //出栈说明右边遇到了最近的比栈顶元素小的元素
                //所以将栈顶出栈作为矩形的高
                //矩形的右边界是right，左边界是left
                int height = heights[stack[top--]];
                if (top != -1) {
                    left = stack[top] + 1;
                } else {
                    //如果栈空，说明没有更小的元素，左边界就是0
                    left = 0;
                }
                int right = i - 1;
                ans = Math.max(ans, height * (right - left + 1));
            }
            stack[++top] = i;
        }
        //处理没有出栈的元素
        while (top != -1) {
            int left = 0;
            int height = heights[stack[top--]];
            if (top != -1) {
                left = stack[top] + 1;
            } else {
                left = 0;
            }
            //如果没有出栈，说明右边没有比它更低的柱子，右边界直接到
            int right = n - 1;
            ans = Math.max(ans, (right - left + 1) * height);
        }
        return ans;
    }
}