85 Maximal Rectangle

https://leetcode.com/problems/maximal-rectangle/

其实想到思路还是挺简单直接的，不要overthink about optimize

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    if (j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = dp[i][j-1] + 1;
                    }
                }
            }
        }
        
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    int minWid = dp[i][j];
                    for (int k = i; k < m && dp[k][j] != '0'; k++) {
                        minWid = Math.min(minWid, dp[k][j]);
                        int hei = k - i + 1;
                        ans = Math.max(hei*minWid, ans);
                    }
                }
            }
        }
        return ans;
    }
}