LeetCode 85.最大矩形 Python题解

最大矩形

# coding=utf-8
# Creator:Mr.Zhao

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


class Solution1:
    def maximalRectangle(self, matrix):
        if not matrix:
            return
        m = len(matrix)  # 行
        n = len(matrix[0])  # 列
        juxing_all = []
        # 列出所有矩形的可能性
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                juxing_all.append([i, j])
        # print(juxing_all)
        max_junxing = 0
        for i, j in juxing_all:
            # 取出列表中所有可能的矩形
            for x in range(m):
                for y in range(n):
                    temp = 0
                    # x+i等于m就代表取到了最后一行了 剩下不需要了
                    # y+j同理的呢
                    if x + i > m or y + j > n:
                        break
                    # 例如 i j为2 4  matrix[x:x+i] 取出两行 row[y:y+j]取出四列
                    temp_lst = [row[y:y + j] for row in matrix[x:x + i]]
                    # print(i, j, temp_lst)
                    flag = False
                    for lst in temp_lst:
                        if "0" in lst:
                            flag = True
                    if flag:
                        continue  # 一定是continue 因为下一列还要算
                    # print(i, j, temp_lst)
                    for hang in range(len(temp_lst)):
                        for lie in range(len(temp_lst[0])):
                            temp += int(temp_lst[hang][lie])
                    # print(temp_lst)
                    if temp > max_junxing:
                        max_junxing = temp
        # print(max_junxing)
        return max_junxing


class Solution:
    def maximalRectangle(self, matrix) -> int:
        if not matrix: return 0
        m, n = len(matrix), len(matrix[0])
        # 记录当前位置上方连续“1”的个数
        pre = [0] * (n + 1)
        res = 0
        for i in range(m):
            for j in range(n):
                # 前缀和
                pre[j] = pre[j] + 1 if matrix[i][j] == "1" else 0
            print(pre)
            # 单调栈
            stack = [-1]
            for k, num in enumerate(pre):
                while stack and pre[stack[-1]] > num:  # 上一个数字大于当前的数 这个条件满足才是矩形 其实就要计算长度了
                    index = stack.pop()
                    # pre[index]为高
                    # k - stack[-1] - 1 是长度
                    # 为什么要不停的出栈呢 其实比如1322这个来说 13肯定不是矩形了 唯一有矩形可能的就是322了啊
                    res = max(res, pre[index] * (k - stack[-1] - 1))
                stack.append(k)

        return res


matrix = [["1", "0", "1", "0", "0"], ["1", "0", "1", "1", "1"], ["1", "1", "1", "1", "1"], ["1", "0", "0", "1", "0"]]
a = Solution()
# a.maximalRectangle(matrix)

"""
# 假设有一个双重列表
list_of_lists = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12]
]
 
# 取出区域(行1到2，列2到4)的值
region_values = [row[1:3] for row in list_of_lists[0:2]]
print(region_values)  # 输出: [[2, 3], [6, 7]]
"""
"""
    这道题解法有很多啊 可以先看Solution1的解法看的比较简单 要点都注释了 但是会超时
    对于Python来说还有numpy的解法，这个应该不会超时你们可以尝试一下
"""

原文地址：https://blog.csdn.net/weixin_45450206/article/details/142716994

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！