（每日算法）Leetcode --- Maximal Rectangle(最大子矩陣)

（每日算法）Leetcode --- Maximal Rectangle(最大子矩陣)

求在0-1矩陣中找出面積最大的全1矩陣

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

首先，想使用遍歷兩次的暴力方法解決是不靠譜的，先打消這個念頭。

這道題的解法靈感來自於 Largest Rectangle in Histogram 這道題，假設我們把矩陣沿著某一行切下來，然後把切的行作為底面，將自底面往上的矩陣看成一個直方圖。這樣就能轉化為使用我們解決的問題來解決新的問題。直方圖的中每個項的高度就是從底面行開始往上1的數量。

我們只需要構造一個一唯的矩陣存儲，以當前行為底的柱狀圖就可以。在第一次的時候只考慮第一行，在第二次的時候查看第二行的元素，如果是0，那麼當前一唯矩陣置為0，否則加1。

class Solution {
public:
  int largestRectangleArea(vector &h) {  
         stack S;  
         h.push_back(0);  
         int sum = 0;  
         for (int i = 0; i < h.size(); i++) {  
              if (S.empty() || h[i] > h[S.top()]) S.push(i);  
              else {  
                   int tmp = S.top();  
                   S.pop();  
                   sum = max(sum, h[tmp]*(S.empty()? i : i-S.top()-1));  
                   i--;  
              }  
         }  
         return sum;  
    }
  int maximalRectangle(vector > &matrix) {
        if(matrix.size() == 0 || matrix[0].size() == 0)
            return 0;
        int maxArea = 0;
        vector temp(matrix[0].size(), 0);//用來調用輔助函數的參數向量
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[0].size(); j++){ //在每一行都重置輔助向量
                if(matrix[i][j] == '1')
                    temp[j]++;
                else
                    temp[j] = 0; //斷開了，就置零
            }
            int ret = largestRectangleArea(temp);
            maxArea = ret > maxArea ? ret : maxArea; 
        }
        return maxArea;
   }
  };