美文网首页
8.21 - hard - 75

8.21 - hard - 75

作者: 健时总向乱中忙 | 来源:发表于2017-08-22 04:14 被阅读0次

363. Max Sum of Rectangle No Larger Than K

如果是求最大值,用for left in range(N): for right in range(left, N):的双层循环来做,每外层循环的开始是直接用当前的col的值,然后每内层循环的时候把当前col的值加到前一层上,然后针对每一次形成的array做一次求最大值。

花了好长时间才做出来。。。。

class Solution(object):
    def maxSumSubmatrix(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        target = k
        if not matrix:
            return 0
        row = len(matrix)
        col = len(matrix[0])
        m = min(row,col)
        n = max(row,col)
        # indicating sum up in every row or every column
        colIsBig = col > row
        res = -sys.maxint
    
        for i in range(m): # 针对小一层的进行循环
            arr = [0]*n
            # sum from row j to row i
            for j in range(i, -1, -1):
                # traverse every column/row and sum up
                for k in range(n):
                    arr[k] = arr[k]+(matrix[j][k] if colIsBig else matrix[k][j])
                
                prefix_sum = 0
                h = [0]
                #print arr
                for k in range(n):
                    prefix_sum += arr[k]
                    # 首先找到prefix_sum插入的位置
                    index = bisect.bisect_left(h, prefix_sum-target)
                    if index < len(h):
                        res = max(res,prefix_sum-h[index])
                    # insert prefix_sum into h and keep the order
                    insert_index = bisect.bisect_left(h, prefix_sum)
                    h.insert(insert_index, prefix_sum)
        return res

相关文章

  • 8.21 - hard - 75

    363. Max Sum of Rectangle No Larger Than K 如果是求最大值,用for l...

  • 8.21 - hard - 74

    358. Rearrange String k Distance Apart 这道题就是把所有值都进行最大区分,在...

  • 8.21 - hard - 79

    407. Trapping Rain Water II 利用外围边界,依次朝里面找,只是新加入heap的值需要取其...

  • 8.21 - hard - 80

    410. Split Array Largest Sum 有两种解法: 按值二分: 左边界是array里的最大值,...

  • 8.21 - hard - 72

    352. Data Stream as Disjoint Intervals 有序的几个重要数据结构和算法:hea...

  • 8.21 - hard - 73

    354. Russian Doll Envelopes 简单的DP的话,会TLE,worst case O(n^2...

  • 8.21 - hard - 76

    381. Insert Delete GetRandom O(1) - Duplicates allowed 设计...

  • 8.21 - hard - 77

    391. Perfect Rectangle 找出四个边角点。 所有的小矩形面积和等于大矩形面积 除了四个边角点,...

  • 8.21 - hard - 78

    403. Frog Jump首先做出来一个TLE的版本,因为这里面要search三种情况,可以用记忆化搜索来做。

  • 我的生日,不想和任何人分享

    8.21

网友评论

      本文标题:8.21 - hard - 75

      本文链接:https://www.haomeiwen.com/subject/tplkdxtx.html