题解 | #求最大子矩阵的大小#

package com.wyj.ch1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

/**

• @author： wyj
• @describe：
• @version：V01
• @date： 2021/7/1- 20:53
• /

public class haha9 {
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(maxArea,maxRecFromBottom(height));
}

    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();//取出栈顶，height最大
            //弹出位置的左最近位置，弹出位置的下面一个
            //向左最多扩展到k+1
            int k=stack.isEmpty()?-1:stack.peek();
            //当前位置i[的元素]比弹出位置j[的元素]小
            //向右最多扩展到i-1    i-1-(k+1)+1=i-k-1
            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;
}

public static void main(String[] args)throws IOException {
    BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
    String[] line1= in.readLine().split(" ");
    int m=Integer.parseInt(line1[0]);    //行
    int n=Integer.parseInt(line1[1]);    //列
    int[][]data=new int[m][n];
    for(int i=0;i<m;i++){
        String[] arr =new String[n];
        arr =in.readLine().split(" ");
        for(int j=0;j<n;j++){
            data[i][j]=Integer.parseInt(arr[j]);
        }
    }

    int result=maxRecsize(data);
    System.out.println(result);
}

}