【leetcode刷题】T23-最大矩形

木又AI帮

修改于 2019-07-18 09:52:20

4430

修改于 2019-07-18 09:52:20

文章被收录于专栏：木又AI帮

【英文题目】（学习英语的同时，更能理解题意哟~）

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:

【中文题目】

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

示例:

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

【思路】

如果明白【T22-柱状图中最大的矩形】这道题的思路，那么本题的想法就很自然了：对于每一行，将其转换为柱状图，计算最大矩形面积即可。时间复杂度为O(n^2)。

（柱状图中计算矩形面积，需要使用一个栈，栈顶到栈底元素从大到小，这样每遇到一个比栈顶元素小的元素，则弹出栈，计算矩形面积，返回面积最大值即可。）

本题还可以使用动态规划来完成，待以后刷题时再来解决。

【代码】

python版本

class Solution(object):
    def update(self, ls, matrix, i):
        for j, m in enumerate(matrix[i]):
            ls[j] = ls[j] +  if m == '1' else 
        return ls

    def cal_value(self, heights):
        heights.append(-1)
        stack = []
        res = 
        for i, h in enumerate(heights):
            while(len(stack) >  and h <= heights[stack[-1]]):
                a = heights[stack.pop()]
                j = stack[-1] if len(stack) >  else -1
                # print(a, i-j-1)
                res = max(res, a * (i-j-1))
            stack.append(i)
        return res

    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if len(matrix) ==  or len(matrix[]) == :
            return 
        ls = [] * len(matrix[])
        res = 
        # 对于每一行
        for i in range(len(matrix)):
            # 更新ls，并计算最大矩形
            ls = self.update(ls, matrix, i)
            res = max(res, self.cal_value(ls))
        return res

C++版本

class Solution {
public:
    int cal_value(vector<int> heights){
        stack<int> ls;
        int res = ;
        heights.push_back(-1);
        for(int i=; i < heights.size(); i++){
            while(ls.size() >  && heights[i] <= heights[ls.top()]){
                int a = heights[ls.top()];
                ls.pop();
                int j = -1;
                if(ls.size() > )
                    j = ls.top();
                if(res < a * (i - j - ))
                    res = a * (i - j - );
            }
            ls.push(i);
        }
        return res;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size() ==  or matrix[].size() == )
            return ;
        vector<int> ls(matrix[].size(), );
        int res = ;
        // 每行转换为柱状图，计算最大面积
        for(int i=; i < matrix.size(); i++){
            for(int j=; j < matrix[].size(); j++){
                if(matrix[i][j] == '0')
                    ls[j] = ;
                else
                    ls[j]++;
            }
            res = max(res, cal_value(ls));
        }
        return res;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-03-27，如有侵权请联系 cloudcommunity@tencent.com 删除

c++