85.Maximal Rectangle

Tags: Hard Stack Dynamic Programming Array Hash Table

Links: https://leetcode.com/problems/maximal-rectangle/

---

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

---

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

        const int INF = 0x0ffffff;
        // for (int i = 0; i < m; ++i) {
        //     for (int j = 0; j < n; ++j) {
        //         if (!matrix[i][j]) matrix[i][j] = -INF;
        //     }
        // }

        int res = 0;
        for (int i = 0; i < m; ++i) {
            vector<int> d(n, 0);
            for (int j = i; j < m; ++j) {
                for (int k = 0; k < n; ++k) {
                    if (matrix[j][k] == '0' || d[k] == -INF) d[k] = -INF;
                    else d[k] += matrix[j][k] - '0';
                }
                //cout << d << endl;

                int tmpMax = 0;
                int sum = 0;
                for (int k = 0; k < n; ++k) {
                    if (d[k] == -INF) {
                        tmpMax = max(sum, tmpMax);
                        sum = 0;
                    }
                    else sum += d[k];
                }
                tmpMax = max(sum, tmpMax);

                res = max(res, tmpMax);
            }
        }

        return res;
    }
};

这个题目输入有个坑点，存储的类型是字符，一开始想当然的以为存储的是int类型，导致测试用例一直WA。

其实这个题目是柱状图里找最大子矩形的变形，最优解法肯定是使用单调栈的方法，额外的可以采用笛卡尔树的方法。另外自己想出来一种从最大子矩形和演变过来的方法。相当于将二维压缩成一维，然后在一维的情形找最长连续为1的序列，求其和。

---

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

        int res = 0;
        vector<int> num(n);
        for (int i = 0; i < m; ++i) {
            num.resize(n);
            for (int j = 0; j < n; ++j) {
                num[j] = (matrix[i][j] == '0' ? 0 : 1 + num[j]);
            }
            res = max(res, maxRectangle(num));
        }

        return res;
    }

    int maxRectangle(vector<int> & num)
    {
        num.push_back(-1);
        stack<int> s;
        int res = 0;
        for (int i = 0; i < num.size(); ++i) {
            while (!s.empty() && num[i] < num[s.top()]) {
                int cur = s.top(); s.pop();
                res = max(res, num[cur] * (s.empty() ? i : i - s.top() - 1));
            }
            s.push(i);
        }
        return res;
    }
};

相当于把84题扩展到二维，很容易联想到363题，每次去累加，但是这里需要注意一点，组成矩阵的必须全是1，那么遇到0相当于就是阻断了矩形在垂直方向的生长，其实就免去了类似363的循环累加。

---

还可以用悬线法来做：https://oi-wiki.org/misc/largest-matrix/