Java 8 ms solution beats 96%


  • 0

    Use solution code from https://leetcode.com/problems/largest-rectangle-in-histogram/

        public int maximalRectangle(char[][] matrix) {
            if (matrix.length == 0)
                return 0;
            int h[] = new int[matrix[0].length], max = 0;
            for (int r = 0; r < matrix.length; r++) {
                for (int i = 0; i < h.length; i++)
                    h[i] = matrix[r][i] == '1' ? h[i] + 1 : 0;
                max = Math.max(max, largestRectangleArea(h));
            }   
            return max;
        }   
    
        public int largestRectangleArea(int[] h) {
            int stack[] = new int[h.length], size = 0, max = 0;
            for (int i = 0; i < h.length; i++) {
                if (size == 0 || h[stack[size - 1]] < h[i])
                    stack[size++] = i;
                while (size > 0 && h[stack[size - 1]] >= h[i])
                    max = Math.max(max, h[stack[--size]] * (i - (size == 0 ? 0 : stack[size - 1] + 1))); 
                stack[size++] = i;
            }   
            while (size > 0)
                max = Math.max(max, h[stack[--size]] * (h.length - (size == 0 ? 0 : stack[size - 1] + 1))); 
            return max;
        }
    

Log in to reply
 

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