general solution based on "Maximum Rectangle in Histogram" Algorithm


  • 0

    According to this "Maximum Rectangle in Histogram" Algorithm, it can solve "Maximal Rectangle" problem, so I change a little bit code to calculate the square area.

    public class Solution {
        public int maximalSquare(char[][] matrix) {
            if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
            int[] height = new int[matrix[0].length];
            for(int i = 0; i < matrix[0].length; i ++){
                if(matrix[0][i] == '1') height[i] = 1;
            }
            int result = largestInLine(height);
            for(int i = 1; i < matrix.length; i ++){
                resetHeight(matrix, height, i);
                result = Math.max(result, largestInLine(height));
            }
            return result;
        }
        
        private void resetHeight(char[][] matrix, int[] height, int idx){
            for(int i = 0; i < matrix[0].length; i ++){
                if(matrix[idx][i] == '1') height[i] += 1;
                else height[i] = 0;
            }
        }    
        
        public int largestInLine(int[] height) {
            if(height == null || height.length == 0) return 0;
            int len = height.length;
            Stack<Integer> s = new Stack<Integer>();
            int maxArea = 0;
            for(int i = 0; i <= len; i++){
                int h = (i == len ? 0 : height[i]);
                if(s.isEmpty() || h >= height[s.peek()]){
                    s.push(i);
                }else{
                    int tp = s.pop();
                    int squareH = height[tp];
                    int squareW = s.isEmpty() ? i : i - 1 - s.peek();
                    
                    maxArea = Math.max(maxArea, squareH >= squareW ? squareW*squareW : squareH*squareH );
                    i--;
                }
            }
            return maxArea;
        }
    }
    

Log in to reply
 

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