Leetcode(84) Largest Rectangle in Histogram

发表于 | 分类于

Description

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

img
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

img
The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

1
2
Input: [2,1,5,6,2,3]
Output: 10

解法

貌似是一道单调栈的题目，网上看到了一个很好的解释：

1、如果已知height数组是升序的，应该怎么做？

比如1,2,5,7,8

那么就是(1*5) vs. (2*4) vs. (5*3) vs. (7*2) vs. (8*1)（类似于从当前位置向后看）

也就是max(height[i]*(size-i))

2、使用栈的目的就是构造这样的升序序列，按照以上方法求解。

但是height本身不一定是升序的，应该怎样构建栈？

比如2,1,5,6,2,3

（1）2进栈。s={2}, result = 0

（2）1比2小，不满足升序条件，因此将2弹出，并记录当前结果为2*1=2。将2替换为1重新进栈。s={1,1}, result = 2

（3）5比1大，满足升序条件，进栈。s={1,1,5},result = 2

（4）6比5大，满足升序条件，进栈。s={1,1,5,6},result = 2

（5）2比6小，不满足升序条件，因此将6弹出，并记录当前结果为6*1=6。s={1,1,5},result = 6，2比5小，不满足升序条件，因此将5弹出，并记录当前结果为5*2=10（因为已经弹出的5,6是升序的）。s={1,1},result = 10，2比1大，将弹出的5,6替换为2重新进栈。s={1,1,2,2,2},result = 10

（6）3比2大，满足升序条件，进栈。s={1,1,2,2,2,3},result = 10

栈构建完成，满足升序条件，这里为了简化处理，在数组的最后加入0，使得最后的递增数组能够完成运算，综上所述，result=10

具体代码如下：

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
class Solution {
    public int largestRectangleArea(int[] heights) {
        int res = 0;
        Stack<Integer> s = new Stack();
        int[] h = new int[heights.length + 1];
        for (int i = 0; i < h.length; i++) {
            if (i < heights.length) {
                h[i] = heights[i];
            } else {
                h[i] = 0;
            }
        }
        for (int i = 0; i < h.length; i++) {
            if (s.empty() || h[i] > s.peek()) {
                s.push(h[i]);
            } else {
                int count = 0;
                while (!s.empty() && s.peek() > h[i]) {
                    count++;
                    res = Math.max(res, s.peek() * count);
                    s.pop();
                }
                while (count > 0) {
                    s.push(h[i]);
                    count--;
                }
                s.push(h[i]);
            }
        }
        return res;
    }
}