题目描述

单调栈：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;
    }
};