题目描述
单调栈:LeetCode 42 和 85 题基本一样。将矩阵看成一个二维矩阵,以每一行为x轴,h[j]是该列的高度。
C++ 代码
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int n = matrix.size();
if (!n) return 0;
int m = matrix[0].size();
auto a = matrix;
vector<int> h(m + 1, 0);
int res = 0;
for (int i = 0; i < n; i ++) {
for (int j = 0; j < m; j ++){
if (a[i][j] == '0') h[j] = 0;
else h[j] ++;
}
stack<int> st;
h[m] = -1;//确保所有元素出栈。
for (int j = 0; j <= m; j ++) {
while (st.size() && h[st.top()] >= h[j]) {
int cur = st.top(); st.pop();
int w = st.empty() ? j : j - st.top() - 1;
if (w <= h[cur])
res = max(res, w * w);//如果长比宽大,那么就是宽的平方。
else
res = max(res, h[cur] * h[cur]);
}
st.push(j);
}
}
return res;
}
};