Maximal Rectangle

Maximal Rectangle

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

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

Thoughts

也是问左右能拓展到多远。相当于是多层的largest rectangle。

Code

/*
 * @lc app=leetcode id=85 lang=cpp
 *
 * [85] Maximal Rectangle
 */
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        const int M = matrix.size(), N = M == 0 ? 0 : matrix[0].size();
        int res = 0;
        vector<int> height(N + 1);
        for (int i = 0; i < M; ++i) {
            stack<int> ind;
            for (int j = 0; j <= N; ++j) {
                if (j == N || matrix[i][j] == '0') height[j] = 0;
                else ++height[j];
                while (!ind.empty() && height[ind.top()] > height[j]) {
                    const int h = height[ind.top()];
                    ind.pop();
                    const int w = ind.empty() ? j : j - ind.top() - 1;
                    res = max(res, h * w);
                }
                ind.push(j);
            }
        }
        return res;
    }
};

Analysis

时间复杂度O(MN), 空间O(N).