Description
Given a rows x cols
binary matrix
filled with 0
’s and 1
’s, find the largest rectangle containing only 1
’s and return its area.
Example 1:
Input: matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]] Output: 6 Explanation: The maximal rectangle is shown in the above picture.
Example 2:
Input: matrix = “0” Output: 0
Example 3:
Input: matrix = “1” Output: 1
Constraints:
rows == matrix.length
cols == matrix[i].length
1 <= row, cols <= 200
matrix[i][j]
is'0'
or'1'
.
Code
Time Complexity: , Space Complexity:
Largest Rectangle in Histogram 的 2D 版本。
以 Example 1 為例,一列一列的來看,第一列就是 [1, 0, 1, 0, 0]
求解 largest rectangle in histogram.
第二列就是 histogram = [2, 0, 2, 1, 1]
,以此類推。
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int n = matrix[0].size();
int res = 0;
vector<int> V(n + 1, 0);
for(int i = 0; i < matrix.size(); i++) {
for(int j = 0; j < matrix[i].size(); j++) {
if(matrix[i][j] == '0') {
V[j] = 0;
} else {
V[j]++;
}
}
// maximum rectangle
stack<int> st;
for(int k = 0; k < V.size(); k++) {
while(!st.empty() && V[st.top()] >= V[k]) {
int h = V[st.top()]; st.pop();
int index = st.empty() ? -1 : st.top();
res = max(res, (k - index - 1) * h);
}
st.push(k);
}
}
return res;
}
};