【题目】

给定整型矩阵map，其中只有0和1两种数值，求其中全是1的所有矩形区域中，最大的矩形区域为1的数量
例如：
1 1 1 0
其中，最大矩形区域有3个1，因此返回3
再比如：
1 0 1 1
1 1 1 1
1 1 1 0
最大矩形区域有6个1，返回6

【解答】

package com.chanmufeng.codingInterviewGuide.stackAndQueue_10;

import java.util.Stack;

public class MaxSubMatrix {

    public static int getMaxRecSize(int[][] map) {
        if (map == null || map.length == 0 || map[0].length == 0)
            return 0;
        int[] height = new int[map[0].length];
        int maxRecSize = 0;

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                height[j] = map[i][j] == 0 ? 0 : height[j] + 1;
            }
            maxRecSize = Math.max(maxRecSize, maxRecFromBottom(height));
        }
        return maxRecSize;
    }

    public static int maxRecFromBottom(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;

        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[i] <= arr[stack.peek()]) {
                int cur = stack.pop();
                int L = stack.isEmpty() ? -1 : stack.peek();
                int curArea = (i - L - 1) * arr[cur];
                maxArea = Math.max(maxArea, curArea);
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            int index = stack.pop();
            int L = stack.isEmpty() ? -1 : stack.peek();
            int curArea = (arr.length - L - 1) * arr[index];
            maxArea = Math.max(maxArea, curArea);
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[][] map = {
                {1, 0, 1, 1},
                {1, 1, 0, 1},
                {1, 0, 1, 0},
        };
        System.out.println(getMaxRecSize(map));
    }
}