85. Maximal Rectangle

Link

Solution

依照以下敘述把每一row轉換成histogram(長條圖)的狀態。

Suppose there is a 2D matrix like

1 1 0 1 0 1

0 1 0 0 1 1

1 1 1 1 0 1

1 1 1 1 0 1

First initiate the height array as 1 1 0 1 0 1, which is just a copy of the first row. Then we can easily calculate the max area is 2.

Then update the array. We scan the second row, when the matrix[1][i] is 0, set the height[i] to 0; else height[i] += 1, which means the height has increased by 1. So the height array again becomes 0 2 0 0 1 2. The max area now is also 2.

然後問題就簡化成84 (Largest Rectangle in Histogram)的問題

 public int maximalRectangle(char[][] matrix) {
        
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        
        int[] temp = new int[matrix[0].length];
        int maxArea = 0;
        for(int i = 0; i < matrix.length; i++){
            handle(temp, matrix[i]);
            maxArea = Math.max(maxArea, getMaxArea(temp));
        }
        return maxArea;
    }
    
    public void handle(int[] temp, char[] row){
        for(int i = 0; i < row.length; i++){
            if(row[i] == '0'){
                temp[i] = 0;
            }else{
                temp[i] = temp[i]+1;
            }
        }
    }
    
    public int getMaxArea(int[] temp){
        
        int maxArea = 0;
        Stack<Integer> s = new Stack<>();
        for(int i = 0 ; i <= temp.length; i++){
            int value = (i == temp.length)? 0 : temp[i];
            if(s.isEmpty() || temp[s.peek()] <= value){
                s.push(i);
            }
            else{
                int height = temp[s.pop()];
                int right = i;
                int left = s.isEmpty()? -1 : s.peek();
                maxArea = Math.max(maxArea, height *(right - left - 1));
                i--;
            }
        }
        return maxArea;
    }