查看: 568|回复: 0

[Java学习] leetcode85. Maximal Rectangle

发表于 2017-8-8 08:00:03
尚学堂AD
题目要求
  1. Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
  2. For example, given the following matrix:
  3. 1 0 1 0 0
  4. 1 0 1 1 1
  5. 1 1 1 1 1
  6. 1 0 0 1 0
  7. Return 6.
复制代码

输入一个二维char数组,其中1代表一个小正方形,求找到数组中最大的矩形面积。

思路一:用二维数组存储临时值

dp的一个思路就是通过存储换效率。也就是说,我将前序遍历过程中的一些有效值存储下来,以供后序遍历参考。从而省去了许多重复遍历,提高效率。这里我使用两个二维int数组来分别记录到matrix[j]为止的最大长度和最大高度。如果matrixi不是最左侧和最上侧的点,还需要判断其所能构成的最大矩形。

  1. public int maximalRectangle(char[][] matrix) {
  2. if(matrix.length==0 || matrix[0].length==0) return 0;
  3. int row = matrix.length;
  4. int column = matrix[0].length;
  5. //最大横向值
  6. int[][] maxRow = new int[row][column];
  7. //最大纵向值
  8. int[][] maxColumn = new int[row][column];
  9. //最大面积
  10. int maximal = 0;
  11. for(int i = 0 ; i<row ; i++){
  12. for(int j = 0 ; j<column ; j++){
  13. if(matrix[i][j]=='1'){
  14. if(i==0 && j==0){
  15. maximal = maxRow[i][j] = maxColumn[i][j] = 1;
  16. }else if(i==0){
  17. maxRow[i][j] = maxRow[i][j-1] + 1;
  18. maxColumn[i][j] = 1;
  19. maximal = Math.max(maxRow[i][j], maximal);
  20. }else if(j==0){
  21. maxColumn[i][j] = maxColumn[i-1][j]+1;
  22. maxRow[i][j] = 1;
  23. maximal = Math.max(maxColumn[i][j], maximal);
  24. //非边缘节点
  25. }else{
  26. maxRow[i][j] = maxRow[i][j-1] + 1;
  27. //所能构成的矩形中以最短边为宽
  28. maxColumn[i][j] = maxColumn[i-1][j]+1;
  29. int tempMaxColumn = maxRow[i][j];
  30. for(int k = 1 ; k <= maxColumn[i][j] ; k++){
  31. tempMaxColumn = Math.min(maxRow[i-k+1][j], tempMaxColumn);
  32. if(tempMaxColumn==1){
  33. maximal = Math.max(maximal, maxColumn[i][j]);
  34. break;
  35. }
  36. maximal = Math.max(maximal, tempMaxColumn * k);
  37. }
  38. }
  39. }
  40. }
  41. }
  42. return maximal;
  43. }
复制代码

在该算法上可以实现的简单优化,是将初始的char[][]数组作为记录maxRow的值,再new一个int[]数组记录当前行maxColumn的值,从而减少了一些存储空间的消耗。核心思路不变,在这里就不贴上代码了。

思路二:栈
  1. public int maximalRectangle2(char[][] matrix) {
  2. if (matrix==null||matrix.length==0||matrix[0].length==0)
  3. return 0;
  4. int cLen = matrix[0].length; // column length
  5. int rLen = matrix.length; // row length
  6. // height array
  7. int[] h = new int[cLen+1];
  8. h[cLen]=0;
  9. int max = 0;
  10. for (int row=0;row<rLen;row++) {
  11. Stack<Integer> s = new Stack<Integer>();
  12. for (int i=0;i<cLen+1;i++) {
  13. if (i<cLen)
  14. if(matrix[row][i]=='1')
  15. h[i]+=1;
  16. else h[i]=0;
  17. if (s.isEmpty()||h[s.peek()]<=h[i])
  18. s.push(i);
  19. else {
  20. while(!s.isEmpty()&&h[i]<h[s.peek()]){
  21. int top = s.pop();
  22. int area = h[top]*(s.isEmpty()?i:(i-s.peek()-1));
  23. if (area>max)
  24. max = area;
  25. }
  26. s.push(i);
  27. }
  28. }
  29. }
  30. return max;
  31. }
复制代码


回复

使用道具 举报