85.Maximal Rectangle---dp

题目链接：https://leetcode.com/problems/maximal-rectangle/description/

题目大意：给出一个二维矩阵，计算最大的矩形面积（矩形由1组成）。例子如下：

法一：将每一行的数据都看成是一个直方图，而每个直方图的高度都是由上一行得到的，例如，上述例子中，从上到下直方图的高度依次是：[1,0,1,0,0],[2,0,2,1,1],[3,1,3,2,2],[4,0,0,3,0]。也就是当当前值是0时，则高度是0；当前值是1时，则高度=上一行的高度+1。这样，对于每一行的直方图可以利用84题的求解办法，这里多的步骤就是将每一行数据转换成直方图，然后再根据每个直方图求解最大矩形面积。代码如下（耗时49ms）：

     public int maximalRectangle(char[][] matrix) {

         if(matrix.length == 0) {

             return 0;

         }

         Stack<Integer> s = new Stack<Integer>();

         int h[] = new int[matrix[0].length];

         int res = 0;

         for(int i = 0; i < matrix.length; i++) {

             for(int j = 0; j < matrix[0].length; j++) {

                 //转换成直方图

                 h[j] = (matrix[i][j] == '1') ? (h[j] + 1) : 0;

                 //根据每个直方图，计算其最大矩形面积，利用84题的方法

                 while(!s.isEmpty() && h[s.peek()] >= h[j]) {

                     int cur = s.pop();

                     res = Math.max(res, h[cur] * (s.isEmpty() ? j : (j - s.peek() - 1)));

                 }

                 s.push(j);

             }

             while(!s.isEmpty()) {

                 int cur = s.pop();

                 res = Math.max(res, h[cur] * (s.isEmpty() ? h.length : (h.length - s.peek() - 1)));

             }

         }

         return res;

     }

法二：dp思想，依旧将每一行的数据看成一个直方图，然后转换成直方图，用left[]数组表示左边界1的位置，用right[]数组表示右边界1的位置。代码如下（耗时13ms）：

     public int maximalRectangle(char[][] matrix) {

         if(matrix.length == 0) {

             return 0;

         }

         int h[] = new int[matrix[0].length];

         int left[] = new int[matrix[0].length], right[] = new int[matrix[0].length];

         //初始化right数组 为matrix[0].length

         for(int i = 0; i < matrix[0].length; i++) {

             right[i] = matrix[0].length;

         }

         int res = 0;

         for(int i = 0; i < matrix.length; i++) {

             int cur_left = 0, cur_right = matrix[0].length;

             //转换成直方图

             for(int j = 0; j < matrix[0].length; j++) {

                 h[j] = (matrix[i][j] == '1') ? (h[j] + 1) : 0;

             }

             //计算左边1的下标

             for(int j = 0; j < matrix[0].length; j++) {

                 if(matrix[i][j] == '1') {

                     left[j] = Math.max(left[j], cur_left);

                 }

                 else {

                     left[j] = 0;

                     cur_left = j + 1;

                 }

             }

             //计算右边1的下标

             for(int j = matrix[0].length - 1; j >= 0; j--) {

                 if(matrix[i][j] == '1') {

                     right[j] = Math.min(right[j], cur_right);

                 }

                 else {

                     right[j] = matrix[0].length;

                     cur_right = j;

                 }

             }

             //计算矩形面积

             for(int j = 0; j < matrix[0].length; j++) {

                 res = Math.max(res, (right[j] - left[j]) * h[j]);

             }

         }

         return res;

     }

巴特西

85.Maximal Rectangle---dp

最新文章

热门文章