每日一题：最大矩形

题意

给定一个仅包含 $0$ 和 $1$ 、大小为 $n * m$ 的二维二进制矩阵，找出只包含 $1$ 的最大矩形，并返回其面积。$(n, m \in [1, 200])$

思路

有一个子问题，求柱状图最大矩形。预先求出 $1-i$ 层的 $h[i]$ 然后利用套用子问题的模板即可，复杂度 $O(n * m)$.

Solution

class Solution {
public:
    int largestRectangleArea(vector<int>& h) {
        stack<int> st;
        st.push(-1);
        int n = h.size();
        vector<int> l(n), r(n, n);
        for (int i = 0; i < n; i++) {
            while (st.top() != -1 && h[st.top()] >= h[i]) {
                r[st.top()] = i;
                st.pop();
            }
            l[i] = st.top();
            st.push(i); 
        }
        int res = 0;
        for (int i = 0; i < n; i++) res = max(res, (r[i] - l[i] - 1) * h[i]);
        return res;
    }
    int maximalRectangle(vector<vector<char>>& a) {
        int n = a.size();
        if (n == 0) return 0;
        int m = a[0].size(), res = 0;
        vector<int> h(m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) 
                h[j] = (a[i][j] == '1' ? h[j] + 1 : 0);
            res = max(res, largestRectangleArea(h));
        }
        return res;
    }
};