16 求最大子矩阵的大小
Table of Contents

ac

import java.util.Scanner;
import java.util.Stack;


public class Main {

    public static Scanner sc = new Scanner(System.in);


    public static int getMaxMatrix(int[] arr, int left, int right){
        Stack<Integer> stack = new Stack<>();
        if(left > right){
            return 0;
        }
        stack.push(left);
        int res = Integer.MIN_VALUE;
        for(int i=left+1;i<=right;i++){
            int stackTop = stack.peek();
            if(arr[i] > arr[stackTop]){
                stack.push(i);
            }else {
                int j = stack.peek();
                while (arr[j] >= arr[i]){
                    stack.pop();
                    int k = stack.isEmpty() ? -1 : stack.peek();
                    res = Math.max(res, (i-k-1) * arr[j]);
                    if(stack.isEmpty()){
                        break;
                    }
                    j = stack.peek();
                }
                stack.push(i);
            }
        }
        int tmpi = right+1;
        while (!stack.isEmpty()){
            int j = stack.peek();
            stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            res = Math.max(res, (tmpi-k-1) * arr[j]);
        }
        return res;
    }

    public static void main(String[] args) {

        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] arr = new int[n][m];
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                int val = sc.nextInt();
                arr[i][j] = val;
            }
        }
        int res = Integer.MIN_VALUE;
        int[] height = new int[m];
        for(int i=0;i<n;i++){
            // 对以每一层为底的求解
            if(i== 0) {
                for (int j = 0; j < m; j++) {
                    height[j] = arr[0][j];
                }
            }else {
                for (int j = 0; j < m; j++) {
                    if(arr[i][j] == 0){
                        height[j] = 0;
                    }else {
                        height[j] += arr[i][j];
                    }
                }
            }
            res = Math.max(getMaxMatrix(height, 0, m-1), res);
        }
        System.out.println(res);
    }

}

直方图的最大矩形面积(凹槽最大储水量)