leetcode85 最大矩形

题目

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

示例:

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

分析

动态规划问题，使用一个一维dp数组记录到每一行位置最大连续1的数量。然后对该dp数组使用单调栈解法（leetcode 84题)求解。

代码

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {

        if (matrix.empty()){
            return 0;
        }

        int res = 0;
        vector<int> dp(matrix[0].size(), 0);

        for (int i = 0; i < matrix.size(); i++){
            for (int j = 0; j < matrix[0].size(); j++){
                dp[j] = matrix[i][j] == '0' ? 0 : dp[j] + 1;
            }
            res = max(res, largestRectangleArea(dp));
        }

        return res;
    }

        //单调栈解法
    int largestRectangleArea(vector<int>& nums) {
        stack<int> stk;
        stk.push(-1);

        int top, cur, res = 0;

        for (int i = 0; i < nums.size(); i++){
            while (stk.top() != -1 && nums[stk.top()] > nums[i]){
                top = nums[stk.top()];
                stk.pop();

                cur = top * (i - stk.top() - 1);

                res = max(res, cur);
            }
            stk.push(i);
        }

        while (stk.top() != -1){
            top = nums[stk.top()];
            stk.pop();

            cur = top * (nums.size() - stk.top() - 1);

            res = max(res, cur);
        }

        return res;
    }   
};