Leetcode No.85 最大矩形（单调栈）

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
 输出：6
 解释：最大矩形如上图所示。
示例 2：
 输入：matrix = []
 输出：0
示例 3：
 输入：matrix = [["0"]]
 输出：0
示例 4：
 输入：matrix = [["1"]]
 输出：1
示例 5：
 输入：matrix = [["0","0"]]
 输出：0
提示：
 rows == matrix.length
 cols == matrix[0].length
 0 <= row, cols <= 200
 matrix[i][j] 为 '0' 或 '1'

import java.util.Deque;
import java.util.LinkedList;

public class Solution3 {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length<=0)
            return 0;
        int cols = matrix[0].length;
        int[] heights = new int[cols+2];
        // 在左右两侧添加两个哨兵
        // 左侧的哨兵使得不用判空
        heights[0] = 0;
        // 尾部的哨兵能在遍历结束时弹出前面的柱子计算面积
        heights[cols+1] = 0;
        int max=0;
        //可以把每一行当作一组height然后求得每一行得最大矩形，然后不断增加行，不断更新height
        for(int row=0;row<matrix.length;row++){
            //转化为柱状图
            for(int j=0;j<cols;j++){
                if(matrix[row][j]=='1'){
                    heights[j+1]++;
                }else
                    heights[j+1] = 0;
            }
            //求的每一行作为最底层的最大矩形,更新最大值
            max = Math.max(max,largestRectangleArea(heights));
        }
        return max;
    }
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if(len==0)
            return 0;
        if(len==1)
            return heights[0];

        Deque<Integer> deque = new LinkedList<>();
        int max = 0;
        // 添加哨兵，使得不用判断空
        deque.addLast(0);
        for(int i=1;i<len;i++){
            // 形成递增单调栈，弹出比当前元素大的元素
            // 同时开始计算前面不同高度的矩形面积，因为当前元素是前面矩形的宽度的边界
            while(heights[i]<heights[deque.peekLast()]){
                // 以当前柱子高度作为矩形的高度
                int currHeight = heights[deque.pollLast()];
                while(currHeight==heights[deque.peekLast()])
                    deque.pollLast();
                // 得到矩形左边的边界
                int currWidth = i - deque.peekLast() -1;
                max = Math.max(max, currWidth*currHeight);
            }
            deque.addLast(i);
        }
        return max;
    }
}

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].length;
        int[][] left = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    //left[i][j] 为矩阵第 i 行第 j 列元素的左边连续1的数量。
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }

        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '0') {
                    continue;
                }
                int width = left[i][j];
                int area = width;
                for (int k = i - 1; k >= 0; k--) {
                    //当考察以 matrix[i][j] 为右下角的矩形时，我们枚举满足0≤k≤i 的所有可能的 k，此时矩阵的最大宽度就为
                    //left[i][j],left[i−1][j],…,left[k][j]的最小值。
                    width = Math.min(width, left[k][j]);
                    area = Math.max(area, (i - k + 1) * width);
                }
                ret = Math.max(ret, area);
            }
        }
        return ret;
    }
}