10:I[13699,["/_next/static/chunks/6b91a202b724e571.js","/_next/static/chunks/6710f67d945945a1.js","/_next/static/chunks/bde5ef9330c4de2d.js"],"default"] 11:I[25152,["/_next/static/chunks/6b91a202b724e571.js","/_next/static/chunks/6710f67d945945a1.js","/_next/static/chunks/bde5ef9330c4de2d.js"],"default"] 12:T42a,class Solution { public: int maximalRectangle(vector>& matrix) { if (matrix.empty()) return 0; int maxarea = 0; vector dp(matrix[0].size(), 0); for(int i = 0; i < matrix.size(); i++) { for(int j = 0; j < matrix[0].size(); j++) { dp[j] = matrix[i][j] == '1' ? dp[j] + 1 : 0; } maxarea = max(maxarea, largestRectangleArea(dp)); } return maxarea; } int largestRectangleArea(vector& heights) { stack s; s.push(-1); int maxarea = 0; for (int i = 0; i < heights.size(); ++i) { while (s.top() != -1 && heights[s.top()] >= heights[i]) { int h = heights[s.top()]; s.pop(); maxarea = max(maxarea, h * (i - s.top() - 1)); } s.push(i); } while (s.top() != -1) { int h = heights[s.top()]; s.pop(); maxarea = max(maxarea, h * ((int)heights.size() - s.top() - 1)); } return maxarea; } };13:T470,/** * @param {character[][]} matrix * @return {number} */ var maximalRectangle = function(matrix) { if (matrix.length === 0) return 0; let maxarea = 0; let dp = new Array(matrix[0].length).fill(0); const largestRectangleArea = (heights) => { let stack = [-1]; let localMax = 0; for (let i = 0; i < heights.length; ++i) { while (stack[stack.length - 1] !== -1 && heights[stack[stack.length - 1]] >= heights[i]) { let h = heights[stack.pop()]; localMax = Math.max(localMax, h * (i - stack[stack.length - 1] - 1)); } stack.push(i); } while (stack[stack.length - 1] !== -1) { let h = heights[stack.pop()]; localMax = Math.max(localMax, h * (heights.length - stack[stack.length - 1] - 1)); } return localMax; }; for(let i = 0; i < matrix.length; i++) { for(let j = 0; j < matrix[0].length; j++) { dp[j] = matrix[i][j] === '1' ? dp[j] + 1 : 0; } maxarea = Math.max(maxarea, largestRectangleArea(dp)); } return maxarea; };

Time Complexity

Space Complexity