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;
    }
}