package com.stack;

// 给定一个二维数组matrix,其中的值不是0就是1,
//返回全部由1组成的最大子矩形,内部有多少个1
// 测试链接:https://leetcode.com/problems/maximal-rectangle/

import java.util.Stack;

public class MaximalRectangle {
 // 最大子矩形必定以某一行为底,不妨列举所有以第0行、第1行....
 //第N行为底的子矩形并比较内部1的个数
 public static int maximalRectangle(char[][] matrix){
 if (matrix == null || matrix.length == 0 || matrix[0].length == 0 ){
 return 0;
 }
 int N = matrix[0].length;
 int[] height = new int[N];
 // 求最大子矩形内部的个数就相当于求最大子矩形的面积
 int maxCount = 0;
 for (int i = 0; i < matrix.length; i++) {
 for (int j = 0; j < N; j++) {
 height[j] = (matrix[i][j] == '0' ? 0 :height[j]+1);
 }
 maxCount = Math.max(maxCount,maxRecFromBottom(height));
 }
 return maxCount;
 }
 public static int maxRecFromBottom(int[] height){
 if (height == null || height.length == 0){
 return 0;
 }

 Stack<Integer> stack = new Stack<>();
 int N = height.length;
 int maxCount = 0;
 for (int i = 0; i < N; i++) {
 while (!stack.isEmpty() && height[stack.peek()] >= height[i]){
 int j = stack.pop();
 int k = (stack.isEmpty() ? -1 : stack.peek());
 int curCount = (i - k -1) * height[j];
 maxCount = Math.max(maxCount,curCount);
 }
 stack.push(i);
 }
 while (!stack.isEmpty()){
 int j = stack.pop();
 int k = (stack.isEmpty() ? -1 : stack.peek());
 int curCount = (N - k -1) * height[j];
 maxCount = Math.max(maxCount,curCount);
 }
 return maxCount;
 }

 public static int maxRecFromBottom2(int[] height){
 if (height == null || height.length == 0){
 return 0;
 }
 int N = height.length;
 int[] stack = new int[N];
 int sIndex = 0;
 int maxCount = 0;
 for (int i = 0; i < N; i++) {
 while (sIndex != -1 && height[stack[sIndex]] >= height[i]){
 int j = stack[sIndex--];
 int k = (sIndex == -1 ? -1 : stack[sIndex]);
 int curCount = (i - k -1) * height[j];
 maxCount = Math.max(maxCount,curCount);
 }
 stack[++sIndex] = i;
 }
 while (sIndex != -1){
 int j = stack[sIndex--];
 int k = (sIndex == -1 ? -1 : stack[sIndex]);
 int curCount = (N - k -1) * height[j];
 maxCount = Math.max(maxCount,curCount);
 }
 return maxCount;
 }
}