85. Maximal Rectangle - Streak 18

row, cols <= 200 이기 때문에,

O(n^3)만 되도 1초 안에 해결 가능하다.

그렇지만 그저께 풀었던 문제를 이용하면, O(n^2)만에 가장 큰 직사각형 넓이를 구할 수 있다.

84. Largest Rectangle in Histogram - Streak 16

 

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] psum = new int[n][m];
        for(int j = 0; j<m; j++){
            psum[0][j] = matrix[0][j] - '0';
            for(int i = 1; i<n; i++){
                psum[i][j] = matrix[i][j] == '1' ? psum[i-1][j] + 1 : 0;
            }
        }

        int ret = 0;
        for(int i = 0; i<n; i++){
            Deque<Tuple> stk = new ArrayDeque<>();
            for(int j = 0; j<m; j++){
                int leftEnd = j;
                while(!stk.isEmpty() && stk.getLast().height() >= psum[i][j]){
                    Tuple before = stk.removeLast();
                    leftEnd = before.index();
                    ret = Math.max(ret, (j - leftEnd)*before.height());
                }
                stk.addLast(new Tuple(psum[i][j], leftEnd));
            }
            while(!stk.isEmpty()){
                Tuple before = stk.removeLast();
                ret = Math.max(ret, (m - before.index())*before.height());
            }
        }
        return ret;
    }
}
record Tuple(int height, int index){

}