LeetCode85号-求最大矩形

/*
解题关键,对二维二进制矩阵的抽象,
我们把它转为一个计算好每个元素左边的1值是连续的个数的矩阵
例如:
{ 
 {0, 0, 0, 1, 1, 1},
 {1, 0, 1, 0, 0, 0},
 {1, 0, 0, 0, 1, 1},
 {0, 0, 1, 1, 1, 1},
 {1, 1, 0, 1, 1, 1}};
 经过我下面写的循环计算每个left[row][col]的值是由left[row][col - 1]+ 1累加而成,
 那我们来看看这个二维数组的最后一列该变成多少呢?
 { 
 {0, 0, 0, 1, 2, 3},
 {1, 0, 1, 0, 0, 0},
 {1, 0, 0, 0, 1, 2},
 {0, 0, 1, 2, 3, 4},
 {1, 2, 0, 1, 2, 3}};
 所以是3,0,2,4,3
 然后再应用LeetCode84号题的解法思路,进行改造,得到如下LeetCode84号题的解.
*/
public class _85_maximal_rectangle {
     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 row = 0; row < m; row++) {
               for (int col = 0; col < n; col++) {
                    if (matrix[row][col] == 1) {
                         left[row][col] = (col == 0 ? 0 : left[row][col - 1]) + 1;
                    }
               }
          }
          int maxArea = 0;
          ArrayDeque<Integer> stack = new ArrayDeque<>();
          for (int col = 0; col < n; col++) {//列固定

               for (int row = 0; row < m; row++) {//完成一个单调递增栈,栈中存行号索引
                    while (!stack.isEmpty() && left[row][col] < left[stack.peek()][col]) {
                         int k = stack.peek();
                         int countDepth = row - k;
                         int newBreadth = left[stack.pop()][col];
                         int countArea = newBreadth * countDepth;
                         maxArea = Math.max(maxArea, countArea);
                    }
                    stack.push(row);
               }
               while (!stack.isEmpty()) {
                    int k = stack.peek();
                    int countDepth = m - k;
                    int newBreadth = left[stack.pop()][col];
                    int countArea = countDepth * newBreadth;
                    maxArea = Math.max(maxArea, countArea);
               }

          }
          return maxArea;
     }

     public static void main(String[] args) {
          _85_maximal_rectangle maximal_rectangle = new _85_maximal_rectangle();
          char[][] ints = {
                  {0, 0, 0, 1, 1, 1},
                  {1, 0, 1, 0, 0, 0},
                  {1, 0, 0, 0, 1, 1},
                  {0, 0, 1, 1, 1, 1},
                  {1, 1, 0, 1, 1, 1}};
          System.out.println(maximal_rectangle.maximalRectangle(ints));

     }
}