leetcode-85. 最大矩形

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例:

1
2
3
4
5
6
7
8
输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

解法：

参考84题

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
class Solution {
    public int maximalRectangle(char[][] matrix) {
        //初始化int数组
        int height = matrix.length;
        if(height==0){
            return 0;
        }
        int width = matrix[0].length;
     
        int[][] temp = new int[height][width];
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                char ch = matrix[i][j];
                int t = ch == '0' ? 0 : 1;
                if (i == 0) {
                    temp[i][j] = t;
                } else {
                    if (matrix[i - 1][j] == '0') {
                        temp[i][j] = t;
                    } else {
                        if (t == 0) {
                            temp[i][j] = 0;
                        } else {
                            temp[i][j] = t + temp[i - 1][j];
                        }
                    }
                }
            }
        }
        //遍历每个数组求最大值
        int max = 0;
        for (int i = 0; i < height; i++) {
            int t = getMaxArea(temp[i]);
            max = max > t ? max : t;
        }
        return max;
    }

    public int getMaxArea(int[] array) {
        int len = array.length;
        if (len == 0) {
            return 0;
        }
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            if (stack.isEmpty()) {
                stack.push(i);
            } else {
                int current = array[i];
                if (current > array[stack.peek()]) {
                    stack.push(i);
                } else {
                    while (!stack.isEmpty() && current <= array[stack.peek()]) {
                        int height = array[stack.pop()];
                        int start = -1;
                        if (!stack.isEmpty()) {
                            start = stack.peek();
                        }
                        int area = height * (i - start - 1);
                        max = max > area ? max : area;
                    }
                    stack.push(i);
                }
            }
        }
        if (!stack.isEmpty()) {
            int end = stack.peek();
            while (!stack.isEmpty()) {
                int height = array[stack.pop()];
                int start = -1;
                if (!stack.isEmpty()) {
                    start = stack.peek();
                }
                int area = height * (end - start);
                max = max > area ? max : area;
            }
        }
        return max;
    }
}