Leetcode85. 最大矩形

题目传送地址：https://leetcode.cn/problems/maximal-rectangle/

运行效率：

代码如下： //哨兵机制+单调栈 解法

class Solution {
    public static int maximalRectangle(char[][] matrix) {
        int maxArea = 0;
        int[] heights = new int[matrix[0].length];
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[0].length; col++) {
                if (matrix[row][col] == '1') {
                    heights[col]++;
                } else {
                    heights[col] = 0;
                }
            }
            int area = largestRectangleArea(heights);
            maxArea = Math.max(area, maxArea);
        }
        return maxArea;
    }

    //哨兵机制+单调栈  解法
    public static int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        //先在数组的首尾各加一个哨兵
        int[] array = new int[heights.length + 2];
        System.arraycopy(heights, 0, array, 1, heights.length);
        //这样一来数组的收尾就各有一个元素的值是0
        for (int i = 0; i < array.length; i++) {
            if (stack.isEmpty()) { //如果栈为空
                stack.push(i);
            } else {  //如果栈不空
                Integer peek = stack.peek();//查看栈顶元素
                //如果栈顶元素的高度大一些
                if (array[peek] > array[i]) {
                    stack.pop();//栈顶元素出栈
                    int width = 0;
                    if (stack.isEmpty()) {  //如果接下来栈里面没有元素了
                        width = heights.length;
                    } else {
                        int left = stack.peek();
                        width = i - left-1;
                    }
                    int area = width * array[peek];
                    maxArea = Math.max(maxArea, area);
                    i = i - 1;
                } else {  //如果栈顶元素小一些，那就继续入栈
                    stack.push(i);
                }
            }
        }
        return maxArea;
    }
}
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