Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- using pi = pair <int, int>;
- int ar[210][210];
- int up[210][210];
- int maximalRectangle(vector<vector<char>>& matrix) {
- int ans = 0;
- int n = matrix.size();
- if(n == 0) return ans;
- int m = matrix[0].size();
- if(m == 0) return ans;
- for(int i=1;i<=n;i++){
- for(int j=1;j<=m;j++){
- if(matrix[i-1][j-1] == '1'){
- ar[i][j] = 1;
- up[i][j] = up[i-1][j] + 1;
- }
- else ar[i][j] = 0;
- }
- }
- for(int i=1;i<=n;i++){
- stack <int> st;
- for(int j=1;j<=m;j++){
- while(!st.empty() and up[i][st.top()] > up[i][j]){
- int area = 0;
- int prej = st.top(); st.pop();
- if(st.empty()) area = up[i][prej] * (j - 1);
- else area = up[i][prej] * (j - st.top() - 1);
- ans = max(ans, area);
- }
- st.push(j);
- }
- while(!st.empty()){
- int area = 0;
- int prej = st.top(); st.pop();
- if(st.empty()) area = up[i][prej] * m;
- else area = up[i][prej] * (m - st.top());
- ans = max(ans, area);
- }
- }
- return ans;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement