题目描述

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

样例

输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

算法

(单调栈) $O(nm)$

1. 将 Largest Rectangle in Histogram 问题扩展到二维。
2. 一行一行考虑，类比 Largest Rectangle in Histogram，一行内所有柱形条的高度 heights 就是当前 (i, j) 位置能往上延伸的最大高度。
3. 直接套用 Largest Rectangle in Histogram 的单调栈算法即可。

时间复杂度

• 枚举每一行的时间复杂度是 $O(n)$，行内单调栈的时间复杂度是 $O(m)$，故总时间复杂度为 $O(nm)。

空间复杂度

• 需要额外 $O(m)$ 的空间存放高度和用于单调栈。

C++ 代码

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size(), m, ans = 0;
        if (n == 0)
            return 0;

        m = matrix[0].size();
        vector<int> heights(m + 1, 0);
        heights[m] = -1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                if (matrix[i][j] == '0')
                    heights[j] = 0;
                else
                    heights[j]++;

            stack<int> st;
            for (int j = 0; j <= m; j++) {
                while (!st.empty() && heights[j] < heights[st.top()]) {
                    int cur = st.top();
                    st.pop();

                    if (st.empty())
                        ans = max(ans, heights[cur] * j);
                    else
                        ans = max(ans, heights[cur] * (j - st.top() - 1));
                }

                st.push(j);
            }
        }

        return ans;
    }
};