85. Maximal Rectangle

increasing stack (largest rectangle in histogram) O(nm)

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int n = matrix.size();
        int m = matrix[0].size();
        vector<int> height(m + 1); // 这里一定要多一个！！方便后边算最大面积
        int res = 0;
        for (int row = 0; row < n; ++row) {
            for (int col = 0; col < m; ++col) {
                height[col] = matrix[row][col] == '0' ? 0 : height[col] + 1;
            }
            res = max(res, helper(height));
        }
        return res;
    }

    int helper(const vector<int> &height) {
        int n = height.size();
        stack<int> s{{-1}};
        int res = 0;
        for (int i = 0; i < n; ++i) {
            while (s.top() != -1 && height[i] < height[s.top()]) {
                int h = height[s.top()];
                s.pop();
                res = max(res, h * (i - s.top() - 1));
            }
            s.push(i);
        }
        return res;
    }
};