Maximal Rectangle

来源：Leetcode

原帖：http://oj.leetcode.com/problems/maximal-rectangle/

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

代码：

 class Solution {  
 public:    
   int maximalRectangle(vector<vector<char> > &matrix) {  
     if (matrix.empty() || matrix[0].empty()) return 0;        
     int M = matrix.size();  
     int N = matrix[0].size();  
     vector<int> height(N + 1, 0); // one more element added  
     int res = 0;  
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         height[j] = (matrix[i][j] == '0') ? 0 : height[j] + 1;          
       }  
       res = max(res, largestRectangleArea(height));  
     }  
     return res;  
   }  
     
   // a little different from 'Largest Rectangle in Histogram'  
   // final 0 is already provided beforehand  
   int largestRectangleArea(const vector<int> &height) {  
     stack<int> stk;  
     int res = 0, i = 0, N = height.size();  
     while (i < N) {  
       if (stk.empty() || height[stk.top()] <= height[i])  
         stk.push(i++);  
       else {  
         int index = stk.top(); stk.pop(); // stack update  
         int width = stk.empty() ? i : i - stk.top() - 1; // stk.top must be descending order  
         res = max(res, width * height[index]);  
       }  
     }  
     return res;  
   }  
 };