Easy Java code for newbee


  • 0

    Good Luck.

    public class Solution {
        public int maximalRectangle(char[][] matrix) {
            if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
                return 0;
                
            int max = 0;
            int[][] heights = new int[matrix.length][matrix[0].length];
            for(int i = 0; i < heights.length; i++)
            {
                for(int j = 0; j < heights[0].length; j++)
                {
                    if(matrix[i][j] == '0')
                        heights[i][j] = 0;
                    else
                    {
                        if(i == 0)
                            heights[i][j] = 1;
                        else
                            heights[i][j] = heights[i-1][j]+1;
                    }
                }
                max = Math.max(max, maxArea(heights[i]));
            }
            return max;
        }
        
        //From the problem largest rectangle in histogram
        public int maxArea(int[] heights)
        {
            int[] arr = new int[heights.length+1];
            for(int i = 0; i < heights.length; i++)
                arr[i] = heights[i];
            arr[arr.length-1] = 0;
            
            Stack<Integer> s = new Stack<Integer>();
            int max = 0;
            int curArea = 0;
            int height = 0;
            int index = 0;
            
            while(index < arr.length)
            {
                if(s.isEmpty() || arr[s.peek()] <= arr[index])
                {
                    s.push(index);
                    index++;
                }
                else
                {
                    height = arr[s.pop()];
                    if(s.isEmpty())
                        curArea = height * index;
                    else
                        curArea = height * (index - s.peek() - 1);
                    max = Math.max(max, curArea);
                }
            }
            return max;
        }
    }
    

Log in to reply
 

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