一维二维数组的区域和问题

力扣53、363等

Posted by songjiu on August 19, 2019

求一维二维数组当中满足条件的某个子区域,一般包括求最大值,或者满足要求的某个值这两种情况。

一维数组

主要还是应用dp的思想,只不过在求满足要求的值时,可以用二分查找降低时间复杂度。

一维数组求最大连续值

lc53

    def maxSubArray(self, nums: List[int]) -> int:
        #每一个对象要么是它本身,要么是他之前字串的和,这取决于他们谁大
        #时间复杂度o(N)
        for i in range(1, len(nums)):
            nums[i]= max(nums[i-1]+nums[i], nums[i])
        return max(nums)

一维数组求满足要求的值

如求一维数组当中≤k的最大值诸如此类,遍历数组当中的累加和,并将其放入list当中排序(可用bisect),之所以list当中初始值有一个0是因为可以保证选出正好为k的子序列。

        #时间复杂度o(N*log(N)) 遍历n遍,查找logn
        temp=[1,-4,2,7,5,1,-3,9]#测试用例
        dp=[0]
        csum=0
        res=-sys.maxsize
        l,r=-1,-1#记一下从哪到哪,实则没用
        for i in range(len(temp)):
            csum+=temp[i]
            idx = bisect.bisect_left(dp, csum-k)
            if idx<len(dp):
                if res<csum-dp[idx]:
                    l,r=dp[idx],i
                    res=max(res,csum-dp[idx])
            bisect.insort(dp,csum)
        return res

二维数组

二维数组需要使用一个叫做Kadanes算法,将其转换为一维数组,再使用上述方法解决,网上搜了搜有个印度小哥的视频挺好! 视频地址

二维数组求最大的子矩阵

通过Kadanes算法,再结合一维数组求最大值的dp方法,即可。

二维数组求满足要求的子矩阵

通过Kadanes算法,再结合一维数组求特定值的方法,即可。
有一个小问题,一开始直接使用一维的方法,发现超时,后来发现,由于该算法的时间复杂度是M*M*N*log(N),所以当M与N相差较大的时候,应该把矩阵较长的那个边作为N,比如最后一个样例就是矩阵列长远大于行长,因此超时,所以加入一个判断行列长度的代码。

    def getexact(self,temp,k):#这里直接用一维的方法
        dp=[0]
        csum=0
        res=-sys.maxsize
        for i in range(len(temp)):
            csum+=temp[i]
            idx = bisect.bisect_left(dp, csum-k)
            if idx<len(dp):
                res=max(res,csum-dp[idx])
            if res==k:
                return k
            bisect.insort(dp,csum)
        return res
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        if len(matrix)==0 or len(matrix[0])==0:
            return 0
        res=-sys.maxsize
        M,N=len(matrix),len(matrix[0])#判断
        if N>M:
            for i in range(len(matrix)):
                temp=matrix[i]
                res=max(res,self.getexact(temp,k))
                if res==k:
                    return k
                for j in range(i+1,len(matrix)):
                    for l in range(len(matrix[j])):
                        temp[l]+=matrix[j][l]
                    res=max(res,self.getexact(temp,k))
                    if res==k:
                        return k
        else:
            for i in range(len(matrix[0])):
                temp=[j[i] for j in matrix]
                res=max(res,self.getexact(temp,k))
                if res==k:
                    return k
                for m in range(i+1,len(matrix[0])):
                    for l in range(len(matrix)):
                        temp[l]+=matrix[l][m]
                    res=max(res,self.getexact(temp,k))
                    if res==k:
                        return k
        return res