leetcode-84. 柱状图中最大的矩形

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

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

img

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

img

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

1
2
输入: [2,1,5,6,2,3]
输出: 10

解法一：遍历每一种可能的高度（n*n）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int largestRectangleArea(int[] heights) {
        int max=0;
        int len=heights.length;
        for(int i =0;i<len;i++){
            int num=heights[i];
            int start = i;
            int end = i;
            while(start>=0 && heights[start]>=num){
                start--;
            }
            while(end<len && heights[end]>=num){
                end++;
            }
            int total=num*(end-start-1);
            max=max>total?max:total;
        }
        return max;
    }
}

解法二：使用递增栈(2*n)

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
42
class Solution {
    public static int largestRectangleArea(int[] heights) {
        if(heights.length==0){
            return 0;
        }
        int max = 0;
        Stack<Integer> stack = new Stack();
        stack.push(0);
        int len = heights.length;
        for (int i = 1; i < len; i++) {
            int current = heights[i];
            int stackTop = heights[stack.peek()];
            if (current > stackTop) {
                stack.push(i);
            } else {
                while (!stack.isEmpty() && heights[stack.peek()] >= current) {
                    Integer topIndex = stack.pop();
                    int start = -1;
                    if (!stack.isEmpty()) {
                        start = stack.peek();
                    }
                    int area = heights[topIndex] * (i - start - 1);
                    max = max > area ? max : area;
                }
                stack.push(i);
            }
        }
        if (!stack.isEmpty()) {
            Integer top = stack.peek();
            while (!stack.isEmpty()) {
                int height = heights[stack.pop()];
                int start = -1;
                if (!stack.isEmpty()) {
                    start = stack.peek();
                }
                int area = height * (top - start);
                max = max > area ? max : area;
            }
        }
        return max;
    }
}