python leetcode 363. Max Sum of Rectangle No Larger Than K

python leetcode 363. Max Sum of Rectangle No Larger ThanKは自分でコードTLEをコードして他の人のコードを研究して時間の複雑さをO(mn)^2からnnm*log(m)に下げることに成功しましたここでmは総裁列の長さの中で大きいもので、列が長いならスキャン列はbisectを利用して二分検索します.挿入(slist)sumsは、行が重畳されたサイズ(xからy行のz番目の列の和)numであり、xからy行の0からz列の和コアコードが格納される

if num<=k: ans=max(ans,num)
i = bisect.bisect_left(slist,num-k)
if i!=len(slist): ans=max(ans,num-slist[i])
bisect.insort(slist,num)

if num<=k:ans=max(ans,num)という文はi=bisect.bisect_left(slist,num-k)num>kのときにxからy行のある列からz列への和if iを検索!=len(slist):ans=max(ans,num-slist[i])i!=slistの長さはbisect.を見つけることができます.insort(slist,num)現在の和をslistに挿入

class Solution:
    def maxSumSubmatrix(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        #         sum[:i] sum[i:]
        m=len(matrix)
        if m==0:
            return 0 
        n=len(matrix[0])
        M = max(m,n)
        N = min(m,n)
        ans = None
        for x in range(N):
            sums=[0]*M
            for y in range(x,N):
                slist,num=[],0 
                for z in range(M):
                    #   
                    sums[z] += matrix[z][y] if m>n else matrix[y][z]
                    num+=sums[z]
                    if num<=k: ans=max(ans,num)
                    i = bisect.bisect_left(slist,num-k)
                    if i!=len(slist): ans=max(ans,num-slist[i])
                    bisect.insort(slist,num)
        return ans or 0