题目

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 6.

中文版

image.png

解答

/**
 * @author vega
 */
public class Main {
    public static void main(String[] args) {
//        int[][] map = new int[][]{{1, 1, 1, 0}};
        int[][] map = new int[][]{
                {1, 0, 1, 1},
                {1, 1, 1, 1},
                {1, 1, 1, 0},
                {1, 0, 1, 0},
                {1, 1, 1, 0}
        };
        int result = solution(map);
        System.out.println(result);
    }

    private static int solution(int[][] map) {
       if (map == null) 
            return 0;
        int max = 0;
        int[] height = new int[map[0].length];
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                height[j] = map[i][j] > 0 ? height[j] + 1 : 0;
            }
            max = Math.max(max, getMaxRexSizeFromBottom(height));
        }
        return max;
    }
    private int getMaxRexSizeFromBottom(int[] height) {
        int max = 0;
        Stack<Integer> s = new Stack<Integer>();
        for (int i = 0; i < height.length; i++) {
            while (!s.isEmpty() && height[s.peek()] >= height[i]) {
                int current = s.pop();
                int top = s.isEmpty() ? -1 : s.peek();
                max = Math.max(max, (i - top - 1) * height[current]);
            }
            s.push(i);
        }
        while (!s.isEmpty()) {
            int current = s.pop();
            int top = s.isEmpty() ? -1 : s.peek();
            max = Math.max(max, (height.length - top - 1) * height[current]);
        }
        return max;
    }
}