矩阵相关

面试题 17.24. 最大子矩阵

给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。

返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。

注意：本题相对书上原题稍作改动

示例：

输入：
[
   [-1,0],
   [0,-1]
]
输出：[0,1,0,1]
解释：输入中标粗的元素即为输出所表示的矩阵

class Solution:
    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:
        n=len(matrix)
        m=len(matrix[0])
        res=[0]*4
        max_sum=matrix[0][0]
        r1=c1=0
        for i in range(n):
            b=[0]*m
            for j in range(i,n):
                sum=0 
                for k in range(m):
                    b[k]+=matrix[j][k]
                    if sum>0:
                        sum+=b[k]
                    else:
                        sum=b[k]
                        r1=i
                        c1=k
                    if sum>max_sum:
                        max_sum=sum
                        res[0],res[1],res[2],res[3]=r1,c1,j,k
        return res

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        '''
        本质思路就是对一个元素i分别找到左和右都小于i的下标 用一个单调栈就能满足左边，右边到遍历到元素j且j小于栈顶时满足要求
        '''
        stack=[]
        heights=[0]+heights+[0]
        res=0
        for i in range(len(heights)):
            while stack and heights[i]<heights[stack[-1]]:
                tmp=stack.pop()
                res=max(res,(i-stack[-1]-1)*heights[tmp])
            stack.append(i)
        return res

85. 最大矩形

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

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:return 0
        def help(heights):
            heights=[0]+heights+[0]
            stack=[]
            ans=0
            for i in range(len(heights)):
                while stack and heights[i]<heights[stack[-1]]:
                    tmp=stack.pop()
                    ans=max(ans,(i-stack[-1]-1)*heights[tmp])
                stack.append(i)
            return ans
        res=0
        heights=[0 for _ in range(len(matrix[0]))]
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if matrix[i][j]=='0':
                    heights[j]=0
                else:
                    heights[j]+=1
            res=max(res,help(heights))
        return res