# 85 Maximal Rectangle

給一個2d array，值只有0和1找出其中最大的由1組成的長方形面積

• idea:
  一開始想過最佳解應該可以達到O(mn)，拜訪過所有格子之後就可以得到答案。用dp紀錄的方式，根據以前dp的經驗，想說應該要記走到該格時的最大面積（我們要求的目標），但思考更新dp方式時發現，這種記錄方法沒辦法紀錄每格最大面積的方向性。
  後來還是看了別人的解法，發現可以把這題想成histogram中的最大長方形。用一個寬度和此2d array相同的1d array來記錄當前這個row形成的histogram，並求此histogram覆蓋的最大長方形面積。

• Pseudocode:

          int[] histogram = new int[width]
          int max = MIN_VALUE
          read matrix row by row
              for each col in current row,
                  if current col != 0
                      histogram[i] += 1
                  else
                      histogram[0] = 0
                  rec = calculateRec(histogram);
                  max = max > rec ? max : rec
          return max
  
          calculateRec(histogram):
              int max = MIN_VALUE
              int curMin = -1;
              int width = 0;
              go through each col
                  if current col != 0
                      update curMin
                      width++;
                  else
                      curMin = -1
                      max = curMin*width > max ? curMin*width : max;
                      width = 0;
              return max
  
      **handle basecase: empty matrix
  

• Code: 求histogram下最大面積直接用#84的code

  public class Solution {
      public int maximalRectangle(char[][] matrix) {
          int height = matrix.length;
          if(height == 0)
              return 0;
          int width = matrix[0].length;
  
          int[] histogram = new int[width];
          int max = Integer.MIN_VALUE;
  
          for(int i=0; i<height; i++){
              for(int j=0; j<width; j++){
                  if(matrix[i][j]!= '0')
                      histogram[j] += 1;
                  else
                      histogram[j] = 0;
              }
              int rec = largestRectangleArea(histogram);
              //printHist(histogram);
              max = Math.max(rec,max);
          }
          return max;
      }
  
      public int largestRectangleArea(int[] heights) {
          Stack<Integer> stack = new Stack<>();
          int maxRec = 0;
          stack.push(-1);
          int i;
          for(i=0; i<heights.length; i++){
              while(stack.peek()!=-1 && heights[stack.peek()] > heights[i]){
                  int curIdx = stack.pop();
                  int rec = heights[curIdx] * (i-stack.peek()-1);
                  maxRec = Math.max(rec,maxRec);
              }
              stack.push(i);
          }
  
          while(stack.peek() != -1){
              int curIdx = stack.pop();
              int rec = heights[curIdx] * (i-stack.peek()-1);
              maxRec = Math.max(rec,maxRec);
          }
  
          return maxRec;
      }
  
      public void printHist(int[] histogram){
          for(int i=0 ; i< histogram.length; i++)
              System.out.print(histogram[i]);
          System.out.println();
      }
  }