LeetCode Q85: Maximal Rectangle (hard)

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

The idea is to scan the matrix row by row. In this row, we calculate a histogram of 1's that are directly continuously above the row. Then we could solve the maximal area of histogram using  "Largest Rectangle in Histogram". Then entire algorithm takes O(n^2) time.

	class Solution {
	public:
	int largestRectangleArea(vector<int>& h) {
	stack<int> s;
	h.push_back(0);
	int p=0;
	int largest=0;
	while(!(s.empty()&&p==h.size()-1)){
	if(s.empty()&&p!=h.size()-1){
	s.push(p);
	p++;
	continue;
	}
	while(h[s.top()]<h[p]){
	s.push(p);
	p++;
	}
	int curTop=s.top();
	s.pop();
	int area;
	if(s.empty())
	area=p*h[curTop];
	else
	area=(p-s.top()-1)*h[curTop];
	largest=area>largest? area: largest;
	}
	return largest;
	}
	int maximalRectangle(vector<vector<char>>& m) {
	if(m.empty())
	return 0;
	int rows=m.size();
	int cols=m[0].size();
	vector<int> hist(cols, 0);
	int largest=0;
	for(int i=0; i<rows; i++){
	for(int j=0; j<cols; j++){
	hist[j]=m[i][j]=='0'? 0:hist[j]+1;
	}
	int area=largestRectangleArea(hist);
	largest=area>largest? area:largest;
	}
	return largest;
	}
	};

view raw Q84.cpp hosted with ❤ by GitHub