221. Maximal Square (Medium)

https://leetcode.com/problems/maximal-square/

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

Solutions

class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int cLen = matrix[0].length;    // column length
        int rLen = matrix.length;       // row length

        // height array
        int[] heights = new int[cLen + 1];
        Arrays.fill(heights, 0);

        int max = 0;

        for (int i = 0; i < rLen; i++) {

            // used to keep increasing heights
            Stack<Integer> stack = new Stack<>();

            for (int j = 0; j < cLen + 1; j++) {
                // The quantity of consecutive 1s in same column counting from current row to above
                if (j < cLen && matrix[i][j] == '1') {
                    heights[j] += 1;
                }

                // 0 cut off the continuity of 1s in same column
                if (j < cLen && matrix[i][j] == '0') {
                    heights[j] = 0;
                }

                // do not push in less taller height
                if (stack.isEmpty() || heights[stack.peek()] <= heights[j]) {
                    stack.push(j);

                    continue;
                }

                while (!stack.isEmpty() && heights[stack.peek()] > heights[j]) {
                    int height = heights[stack.pop()];
                    int width = stack.isEmpty() ? j : (j - 1 - stack.peek());

                    // Square requires same height and width, so here we choose the smallest one as the edge.
                    int min = Math.min(height, width);

                    int area = min * min;

                    max = Math.max(max, area);
                }

                stack.push(j);
            }
        }

        return max;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""