栈和队列——求最大子矩阵的大小

「爱情、让人受尽委屈。」 2022-06-07 10:50 131阅读 0赞

【题目】  
　　给定一个整型矩阵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

【解答】  
　　1、矩阵的行数为N，以每一行做切割，统计以当前行作为底的情况下，每个位置往上为1的数量。使用高度数组height来表示  
　　例如  
　　1 0 1 1  
　　1 1 1 1  
　　1 1 1 0  
　　以第1行做切割后，height=\{1,0,1,1\}，height\[j\]表示目前的底上（第1行），j位置往上（包括j位置）有多少个连续的1。  
　　以第2行做切割后height=\{2,1,2,2\}，注意到从第一行到第二行，height数组的更新是十分方便的，即height\[j\] = map\[i\]\[j\]+1。  
　　以第3行做切割后，height=\{3,2,3,0\}  
　　  
　　2、对于每一次切割 ，都利用更新后的height数组来求出以每一行为第的情况下，最大的矩形是什么。那么这么多次切割后，最大的矩形就是我们要的。讲一下怎么求最大的矩形，利用栈，比如，height是\[3,2,3,0\]，就让他们依次入栈，要求从栈顶到栈底要始终满足从大到小，如果将要入栈的大于栈顶元素，则直接将其压入，如果将要入栈的小于栈顶元素，那就将栈顶元素依次弹出，直到满足入栈的元素大于栈顶元素才让其入栈，那么，注意下面这句话，当出现要入栈的元素小于栈顶元素的时候，将要入栈的元素的位置记为i，栈顶元素为j，栈顶元素下面的元素为k，那么，当前形成的最大的矩形就是(i-k-1)\*height\[j\]，即使在中间的时候有时候会计算错误（具体错误自己琢磨吧），在最后也会被纠正过来  
　　  
　　整个过程就是如下代码中的maxRecSize方法。步骤2的实现是如下代码中的maxRecFromBottom方法，具体的细节自己走代码吧

import java.util.*;
    class test{
        public static void main(String[] args){
            //定义map矩阵
            int[][] map = {
       {
       1,0,1,1},{
       1,1,1,1},{
       1,1,1,0}};
            //调用函数
            int max = maxRecSize(map);
            //输出
            System.out.println(max);
    
        }
    
        public static int maxRecSize(int[][] map){
            //如果是空的，返回
            if(map==null || map.length==0 || map[0].length==0){
                return 0;
            }
            //用来存放最大值，最后返回
            int maxArea = 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?0:height[j]+1;
                }
                //在每一层都计算一遍最大子矩阵，找到最大的
                maxArea = Math.max(maxRecFromBottom(height),maxArea);
            }
            return maxArea;
        }
    
        public static int maxRecFromBottom(int[] height){
            //如果高度数组为空，返回
            if(height==null || height.length==0){
                return 0;
            }
            int maxArea = 0;
            Stack<Integer> stack = new Stack<Integer>();
            for(int i=0;i<height.length;i++){
                while(!stack.isEmpty() && height[i]<=height[stack.peek()]){
                    int j = stack.pop();
                    int k = stack.isEmpty()?-1:stack.peek();
                    int curArea = (i-k-1)*height[j];
                    maxArea = Math.max(maxArea,curArea);
                }
                stack.push(i);
            }
            while(!stack.isEmpty()){
                int j = stack.pop();
                int k = stack.isEmpty()?-1:stack.peek();
                int curArea = (height.length-k-1)*height[j];
                maxArea = Math.max(maxArea,curArea);
            }
            return maxArea;
        }
    }