84. 柱状图中最大的矩形（困难）

Posted on In Views:

1，问题描述

84. 柱状图中最大的矩形

已解答

难度：困难

给定 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 <=10^5
  • 0 <= heights[i] <= 10^4

2，初步思考

​ 最初想到的是dp求解，但是事实上dp求解也并没有好多少！！时间复杂度还是O(n2)

​ 在看了官方题解之后，发现了单调栈（monostone stack）的解法，这种解法的时间复杂度最优，空间换时间

3，代码处理

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
import support.Pair;

import java.util.ArrayDeque;
import java.util.Deque;

public class _84柱状图中最大的矩形 {

    // 解法4:单调栈，时间复杂度O(n)，空间复杂度O(n)
    public int largestRectangleArea_stack(int[] heights) {
        int res = 0;
        int[] heightsNew = new int[heights.length + 2];
        heightsNew[0] = -1;
        heightsNew[heights.length + 1] = -1;
        System.arraycopy(heights, 0, heightsNew, 1, heights.length);
        Deque<Pair<Integer, Integer>> stack = new ArrayDeque<>();
        stack.addLast(new Pair(0, -1));
        for (int i = 1; i < heightsNew.length; i++) {
            int height = heightsNew[i];
            while (stack.peekLast().getValue() > height) {// 需要弹出数据
                Pair<Integer, Integer> pair = stack.pollLast();
                int lenCur = (i - stack.peekLast().getKey() - 1);
                res = Math.max(res, lenCur * pair.getValue());
            }
            stack.addLast(new Pair(i, height));
        }
        return res;
    }

    /**
     * -1, 2, 1, 2, -1
     */


    // 解法3:动态规划，优化空间使用率，超时！！时间复杂度O(n^2)，空间复杂度为O(1)
    // 其实这个dp也不太需要那么多空间使用
    // dp[i][i] = h[i]
    // dp[i][i+1] = min(dp[i][i],h[i+1])*(i+1-i+1)
    public int largestRectangleArea_dp_optimize(int[] heights) {
        int res = 0;
        int len = heights.length;
        int dp = 0;// 这个其实就是dp缓存
        for (int i = 0; i < len; i++) {
            dp = heights[i];
            res = Math.max(res, dp);
            for (int j = i + 1; j < len; j++) {
                dp = Math.min(dp / (j - i), heights[j]) * (j - i + 1);
                res = Math.max(res, dp);
            }
        }
        return res;
    }


    // 解法2：动态规划，将解法1中重复计算的解决掉，时间复杂度O(n^2)，空间复杂度为O(n^2)
    // dp[i][i+1] = min(dp[i][i],h[i+1])*(i+1-i+1)
    // dp[i][j] = min(dp[i][j-1]/(j-1-i),h[j])*(j-i+1)
    public int largestRectangleArea_dp(int[] heights) {
        int res = 0;
        int len = heights.length;
        int[][] dp = new int[heights.length][heights.length];
        for (int i = 0; i < heights.length; i++) {
            dp[i][i] = heights[i];
            res = Math.max(res, dp[i][i]);
        }
        int i = 0, j = 1;
        while (i < j && j < len) {
            dp[i][j] = Math.min(dp[i][j - 1] / (j - 1 - i + 1), heights[j]) * (j - i + 1);
            res = Math.max(res, dp[i][j]);
            if (i == len - 2 && j == len - 1) break;
            if (j == len - 1) {
                i++;
                j = i + 1;
            } else {
                j++;
            }
        }
        return res;
    }

    // 解法1-v2:暴力枚举，优化，时间复杂度为O(n^2)，空间复杂度(1)
    public int largestRectangleArea_brute_optimize(int[] heights) {
        int max = 0;
        for (int i = 0; i < heights.length; i++) {// index,向两边扩散
            int height = heights[i], left = i, right = i;
            do {
                left--;
            } while (left >= 0 && heights[left] >= height);
            do {
                right++;
            } while (right < heights.length && heights[right] >= height);
            max = Math.max(max, (right - left - 1) * height);
        }
        return max;
    }

    // 解法1:暴力枚举，超时，时间复杂度为O(n^3)，有很多重复计算的部分
    public int largestRectangleArea_brute(int[] heights) {
        int max = 0;
        for (int i = 0; i < heights.length; i++) {// left
            for (int j = i; j < heights.length; j++) {// right
                int heightMin = Integer.MAX_VALUE;
                for (int k = i; k <= j; k++) {
                    heightMin = Math.min(heightMin, heights[k]);
                }
                max = Math.max(max, heightMin * (j - i + 1));
            }
        }
        return max;
    }

    public static void main(String[] args) {
        _84柱状图中最大的矩形 largestRectangleArea = new _84柱状图中最大的矩形();
        System.out.println(largestRectangleArea.largestRectangleArea_stack(new int[]{2, 2, 2, 1, 4}));
//        System.out.println(largestRectangleArea.largestRectangleArea_stack(new int[]{2, 1, 5, 6, 2, 3}));
//        System.out.println(largestRectangleArea.largestRectangleArea_stack(new int[]{2, 1, 2}));
//        System.out.println(largestRectangleArea.largestRectangleArea_dp(new int[]{0}));
//        System.out.println(largestRectangleArea.largestRectangleArea_stack(new int[]{0}));
    }
}