85. Maximal Rectangle
給定一個由 0 和 1 填充的 rows x cols 二進制矩陣，找到只包含 1 的最大的矩形並返回其面積。
範例 1：
輸入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 輸出：6 解釋：上圖所示為最大矩形。
Python
from typing import List
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not matrix or not matrix[0]:
return 0
# Initialize variables
max_area = 0
num_cols = len(matrix[0])
heights = [0] * num_cols
for row in matrix:
for i in range(num_cols):
# Update the current row's histogram heights
heights[i] = heights[i] + 1 if row[i] == '1' else 0
# Compute the max area for the current histogram
max_area = max(max_area, self.largestRectangleArea(heights))
return max_area
def largestRectangleArea(self, heights: List[int]) -> int:
stack = []
max_area = 0
heights.append(0) # Append a zero to handle the remaining bars in the stack
for i in range(len(heights)):
while stack and heights[i] < heights[stack[-1]]:
h = heights[stack.pop()]
w = i if not stack else i - stack[-1] - 1
max_area = max(max_area, h * w)
stack.append(i)
heights.pop() # Remove the appended zero
return max_area
17.75MB, 196ms
C++
#include <vector>
#include <stack>
#include <algorithm>
class Solution {
public:
int maximalRectangle(std::vector<std::vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) {
return 0;
}
int max_area = 0;
int num_cols = matrix[0].size();
std::vector<int> heights(num_cols, 0);
for (const auto& row : matrix) {
for (int i = 0; i < num_cols; ++i) {
// Update the current row's histogram heights
heights[i] = row[i] == '1' ? heights[i] + 1 : 0;
}
// Compute the max area for the current histogram
max_area = std::max(max_area, largestRectangleArea(heights));
}
return max_area;
}
private:
int largestRectangleArea(const std::vector<int>& heights) {
std::stack<int> stack;
int max_area = 0;
std::vector<int> extended_heights = heights;
extended_heights.push_back(0);
// Append a zero to handle the remaining bars in the stack
for (int i = 0; i < extended_heights.size(); ++i) {
while (!stack.empty() && extended_heights[i] < extended_heights[stack.top()]) {
int h = extended_heights[stack.top()];
stack.pop();
int w = stack.empty() ? i : i - stack.top() - 1;
max_area = std::max(max_area, h * w);
}
stack.push(i);
}
return max_area;
}
};
19.76MB, 28ms
Javascript
/**
* @param {character[][]} matrix
* @return {number}
*/
var maximalRectangle = function(matrix) {
if (matrix.length === 0 || matrix[0].length === 0) {
return 0;
}
let maxArea = 0;
const numCols = matrix[0].length;
const heights = new Array(numCols).fill(0);
for (let row of matrix) {
for (let i = 0; i < numCols; i++) {
// Update the current row's histogram heights
heights[i] = row[i] === '1' ? heights[i] + 1 : 0;
}
// Compute the max area for the current histogram
maxArea = Math.max(maxArea, largestRectangleArea(heights));
}
return maxArea;
};
function largestRectangleArea(heights) {
const stack = [];
let maxArea = 0;
heights.push(0); // Append a zero to handle the remaining bars in the stack
for (let i = 0; i < heights.length; i++) {
while (stack.length > 0 && heights[i] < heights[stack[stack.length - 1]]) {
const h = heights[stack.pop()];
const w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, h * w);
}
stack.push(i);
}
heights.pop(); // Remove the appended zero
return maxArea;
}
53.48MB, 80ms
