Leetcode 85. Maximal Rectangle

[Woodyiiiiiii]

类似的题型还有：

• 84. Largest Rectangle in Histogram

这种类型的题目，条件一般是：求在一个有限表格中最大矩形面积。

解题思路一般是：

1. 用DP思路求每列积累的高度
2. 用单调栈求解最大面积

难点在于如何使用单调栈。栈内保持元素单调，同时记录的是索引位置，进而在出栈过程中计算长度。单调栈的用处是计算一段连续单调的区间长度。

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int ans = 0;
        int[][] dp = new int[m][n + 1];
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = 1;
                    if (i > 0) {
                        dp[i][j] += dp[i - 1][j];
                    }
                }
            }
            LinkedList<Integer> s = new LinkedList<>();
            int j = 0;
            while (j <= n) {
                if (s.isEmpty() || dp[i][j] > dp[i][s.peek()]) {
                    s.push(j++);
                } else {
                    int t = s.poll();
                    ans = Math.max(ans, dp[i][t] * (s.isEmpty() ? j : j - s.peek() - 1));
                }
            }
        }
        return ans;
    }
}

Tips:

1. 注意重新创建一个长度为n+1的数组副本
2. 单调栈内严格递增
3. 如何计算长度，为什么是j和j-s.peek()-1?