O(n * m)
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); } }
大于栈顶,直接入栈
小于栈顶,遇到小于等于栈中元素的,栈中元素不断的弹出,此时求解一番
直到最后一个元素,再弹出依次处理即可