Given a 2D binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing only 1‘s and return its area.
For example, given the following matrix:
1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
Return 6.
class Solution { private: int largestRectangle(vector<int>& heights){ stack<int> s; heights.push_back(0); int res = 0; int i = 0; while(i < heights.size()){ if(s.empty() || heights[i] > heights[s.top()]){ s.push(i); i++; }else{ int cur = s.top(); s.pop(); if(s.empty()){ res = max(res,i*heights[cur]); }else{ res = max(res,heights[cur]*(i-s.top()-1)); } } } return res; } public: int maximalRectangle(vector<vector<char>>& matrix) { if(matrix.empty()) return 0; int m = matrix.size(); int n = matrix[0].size(); int res = 0; vector<int> heights(n,0); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ heights[j] = matrix[i][j] == ‘0‘? 0 : (1+heights[j]); } res = max(res,largestRectangle(heights)); } return res; } };
原文：http://www.cnblogs.com/wxquare/p/6213310.html