WangBa's Blog

0084. Largest Rectangle in Histogram

LeetCode真的难系列

发布于：2020年11月2日
次浏览

84. Largest Rectangle in Histogram Hard

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

思路：

思路一：暴力破解

  • 先用 HashSet 存储数组中不重复的值，主要是用来加速的，不用也可以，像在本题里面就可以少算一次 2
  • 然后遍历这个 set，再在 set 中进行数组遍历，找到连续比当前值大于或等于的数组值，并找到最大的宽度，像在上面的🌰中，当值为 1 时，遍历一遍后，最大的的宽度为 6

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int largestRectangleArea(int[] heights) {
    Set<Integer> set = new HashSet<>();
    for (int height : heights) {
        set.add(height);
    }
    int res = 0;
    for (int height : set) {
        int width = 0;
        int max = 1;
        for (int value : heights) {
            if (value >= height) {
                width++;
            } else {
                max = Math.max(max, width);
                width = 0;
            }
        }
        max = Math.max(max, width);
        res = Math.max(res, max * (height));
    }
    return res;
}

时间复杂度：O(n^2)

空间复杂度：O(n)

思路二：

这个思路有点和 42题 有点像，可以看下面的🌰：

image-20201104211954756

  • 在思路一中，是将每一个不重复的数组元素和整个数组进行对比，求出最大面积
  • 在 该解法中，仍然是求每个柱子所占的最大面积，最后取最大的即可
  • 红色是当前柱子，分别找到离该柱子左边最近比该柱子低的柱子 leftMin 和右边最近低于该柱子的柱子 rightMin
  • 此时的面积可以计算为：heights[cur] * ( rightMin - leftMin -1)

那么如何求出每一个柱子的 leftMin ，下面的代码是时间复杂度为 O(n)

1
2
3
4
5
6
7
8
9
int[] leftMin = new int[heights.length];
leftMin[0] = -1;
for (int i = 1; i < heights.length; i++) {
    int temp = i - 1;
    while (temp >= 0 && heights[i] <= heights[temp]) {
        temp--;
    }
    leftMin[i] = temp;
}

当然上面的代码是可以降低时间复杂度的，可以看下面这个🌰：

image-20201105202816731
  • 如果我们要求 cur 的 leftMin ，可以放弃一部分比较，具体是哪一部分呢？
  • 如果当前 cur 高度小于 cur - 1 ，那么 leftMin[i - 1] + 1 到 cur - 1 之间所有柱子的高度都是大于 cur 的，因为 leftMin[i - 1] 是第一个比 cur - 1 低的
1
2
3
4
5
6
7
8
9
int[] leftMin = new int[heights.length];
leftMin[0] = -1;
for (int i = 1; i < heights.length; i++) {
    int temp = i - 1;
    while (temp >= 0 && heights[temp] >= heights[i]) {
        temp = leftMin[temp];
    }
    leftMin[i] = temp;
}

代码：

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
public int largestRectangleArea(int[] heights) {
    if (heights.length == 0) return 0;

    int[] leftMin = new int[heights.length];
    leftMin[0] = -1;
    for (int i = 1; i < heights.length; i++) {
        int temp = i - 1;
        while (temp >= 0 && heights[temp] >= heights[i]) {
            temp = leftMin[temp];
        }
        leftMin[i] = temp;
    }

    int[] rightMin = new int[heights.length];
    rightMin[heights.length - 1] = heights.length;
    for (int i = heights.length - 2; i >= 0; i--) {
        int temp = i + 1;
        while (temp <= heights.length -1 && heights[temp] >= heights[i]) {
            temp = rightMin[temp];
        }
        rightMin[i] = temp;
    }

    int max = 0;
    for (int i = 0; i < heights.length; i++) {
        int temp = (rightMin[i] - leftMin[i] - 1) * heights[i];
        max = Math.max(max, temp);
    }

    return max;
}

思路三：栈

  • 当遍历到 cur 时，出现 height[cur] < height[peek] 时，那么 leftMin 一定是 newPeek ，rightMin 就是 cur ，此时面积最大值就是 (cur - leftMin - 1) * height[peek]

image-20201105212528335

代码：

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
public int largestRectangleArea(int[] heights) {
    int max = 0;
    Stack<Integer> stack = new Stack<>();
    int i = 0;
    while (i < heights.length) {
        if (stack.isEmpty()) {
            stack.push(i);
            i++;
        }
        else {
            int peek = stack.peek();
            if (heights[i] >= heights[peek]) {
                stack.push(i);
                i++;
            }
            else {
                int height = heights[stack.pop()];
                int leftMin = stack.isEmpty() ? -1 : stack.peek();
                int area = (i - leftMin - 1) * height;
                max = Math.max(area, max);
            }
        }
    }

    while (!stack.isEmpty()) {
        int height = heights[stack.pop()];
        int leftMin = stack.isEmpty() ? -1 : stack.peek();
        int area = (heights.length - leftMin - 1) * height;
        max = Math.max(area, max);
    }
    return max;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://wangba.me/2020/11/02/0084-Largest-Rectangle-in-Histogram/

更新于：2022年3月26日

Leetcode

Stack

评论