求最大矩形

问题重述：

给定一个整型矩阵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 cn.basic.algorithm;

import java.util.Stack;

/**
 * @author FOLDN
 * 求最大矩形
 */
public class MaxRect {
    public static void main(String[] args) {
        //int[][] map = {{1},{1},{1},{0}};
        int[][] map = {{1,0,1,1},{1,1,1,1},{1,1,1,0}};
        int size = maxRectSize(map);

        System.out.println(size);
    }
    public static int maxRectSize(int[][] map){
        if (map ==null || map.length == 0 || map[0].length == 0){
            return 0;
        }
        // 创建一个int值用来保存最大矩形个数
        int maxArea = 0;
        // 创建一个int数组，用来保存每一列的1的个数
        int[] height = new int[map[0].length];
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                // 当对应位置为1时，该列对应的height+1
                height[j] = map[i][j] == 1 ? height[j]+1 : 0;
            }
            maxArea = Math.max(maxArea,maxRectFromBottom(height));
        }
        return maxArea;
    }
    public static int maxRectFromBottom(int[] height){
        if (height == null || height.length ==0){
            return 0;
        }
        // 创建于给int值来存放最大值0
        int maxArea = 0;
        // 创建一个栈来求得最大矩形
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < height.length; i++) {
            while(!stack.isEmpty() && height[stack.peek()] >= height[i]){
                // 当栈不为空且栈顶元素对应数组值大于当前数组值时，弹出栈顶元素
                Integer index = stack.pop();
                int left = stack.isEmpty() ? -1 : stack.peek();
                int area = height[index]*(i-1-left);
                maxArea = Math.max(area,maxArea);
            }
            // 经过上面的循环，此时加入的数组下标对应的数组值不会破坏栈的单调性
            stack.push(i);
        }
        // 最后栈中可能会存有元素，我们要将这些元素取出来
        while(!stack.isEmpty()){
            Integer index = stack.pop();
            int left = stack.isEmpty() ? -1 :stack.peek();
            int area = height[index]*((height.length-1)-left);

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

        return maxArea;
    }

}

代码解析

​ 代码中定义了两个方法，一个方法是将二维数组的每一行分隔作为矩形的底来判断最大矩形，一个方法是计算最大矩形。我们重点讲第二个方法，第二个方法我们首先创建一个整型变量和一个栈，整型变量用来存放最大矩形，栈用来对数组元素进行排序，找到每一个元素左右的比自己小的最近元素。遍历height数组，在循环中，当栈不为空，且当前数组元素小于栈顶元素对应的数组元素时，将栈顶元素弹出，因为当前元素如果压入栈会破坏栈的单调性（从栈底到栈顶从小到大排列），重复当前操作，直到不破坏栈的单调性的时候，才将当前元素压入栈中。在弹出栈顶元素时，此时的栈顶元素下方为该元素为左边的小于该元素的最近值，将要压入的值为右边的小于该元素的最近值，通过这两个左右的最近值就可以计算最大矩形大小。（在这里面还有一个逻辑问题，当栈顶元素下方没有元素时，说明该元素左边元素都大于他本身，那么我们就可以把其左边的全部算入矩形中）遍历完数组后栈中可能还会存有元素，我们还需要把栈内元素弹出并计算，这时候栈中的元素都是右边没有比他更大的元素了，所以我们在计算时，当前元素右边的所有矩形都要加进来。栈顶元素下方没有元素时把左边所有元素计算进去。

总结：

单调栈：栈内元素按照规则排序，如果压入的元素不符合规则，则弹出队尾元素，直到满足规则。（只能操作栈顶）