Maximal Rectangle

1package pkg5leetcode.top100;2 3/*4 * Maximal Rectangle | LC 855 * APPROACH: Treat each row as histogram base; run LC84 on each row.6 * COMPLEXITY: Time O(m*n), Space O(n)7 */8import java.util.*;9 10public class top100_LC85MaximalRectangle {11    static int maximalRectangle(char[][] matrix) {12        if (matrix.length == 0) return 0;13        int m = matrix.length, n = matrix[0].length;14        int[] h = new int[n], best = 0;15        for (int r = 0; r < m; r++) {16            for (int c = 0; c < n; c++)17                h[c] = matrix[r][c] == '1' ? h[c] + 1 : 0;18            best = Math.max(best, largestRect(h));19        }20        return best;21    }22 23    static int largestRect(int[] heights) {24        Deque<Integer> st = new ArrayDeque<>();25        int best = 0;26        for (int i = 0; i <= heights.length; i++) {27            int h = i == heights.length ? 0 : heights[i];28            while (!st.isEmpty() && h < heights[st.peek()]) {29                int height = heights[st.pop()];30                int w = st.isEmpty() ? i : i - st.peek() - 1;31                best = Math.max(best, height * w);32            }33            st.push(i);34        }35        return best;36    }37 38    public static void main(String[] args) {39        char[][] m = {40            {'1','0','1','0','0'},41            {'1','0','1','1','1'},42            {'1','1','1','1','1'},43            {'1','0','0','1','0'}44        };45        check(maximalRectangle(m) == 6, "case1");46        check(maximalRectangle(new char[][]{{'0'}}) == 0, "case2");47        System.out.println("all tests passed");48    }49 50    static void check(boolean cond, String name) {51        if (!cond) throw new AssertionError("FAILED: " + name);52        System.out.println("  PASS " + name);53    }54}