share my java solution beats 95.37% based on maxRectangleArea problem


  • 0
    S
    public class Solution {
    
         public int maximalRectangle(char[][] matrix) {
            int m = matrix.length;
            int n = m==0? 0:matrix[0].length;
            int[][] heights = new int[m][n];
            int maxArea = 0;
            //initialize the historgram in every row
            for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){
                    if(matrix[i][j] == '0'){
                        heights[i][j] = 0;
                    }else{
                        heights[i][j] = (i==0)? 1:heights[i-1][j]+1;
                    }
                }
            }
            for(int i=0; i<m; i++){
                maxArea = Math.max(maxArea,largestRectangleArea(heights[i]));
            }
            return maxArea;
        }
        public int largestRectangleArea(int[] heights){
            if(heights==null || heights.length==0) return 0;
            int[] left = new int[heights.length];
            int[] right = new int[heights.length];
            int result = 0;
            left[0] = 0;
            for(int i=1; i<heights.length; i++){
                int currLeft = i-1;
                while(currLeft>=0 && heights[currLeft]>=heights[i]){
                    currLeft = left[currLeft]-1;
                }
                left[i] = currLeft+1;
            }
            //build right
            right[heights.length-1] = heights.length-1;
            for(int i=heights.length-2; i>=0; i--){
                int currRight = i+1;
                while(currRight<heights.length && heights[i]<=heights[currRight]){
                    currRight = right[currRight]+1;
                }
                right[i] = currRight-1;
            }
            //compare right
            for(int i=0; i<heights.length; i++){
                result = Math.max(result, (right[i]-left[i]+1)*heights[i]);
            }
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.