题目截图

题目分析

• 最直观的是o(mmnn)的二维前缀和 + 遍历左上右下做法
• 但是会超时
• 考虑固定上下边界，从左到右逐次加入每列框定的和
• 用stl记录所有框定的列前缀和
• 若当前前缀和为s，考虑第一个大于等于s - k的前缀和即可
• 复杂度优化为o(mmnlogn)

ac code

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        from sortedcontainers import SortedList
        ans = -inf
        m, n = len(matrix), len(matrix[0])
        # 枚举上下边界
        # 从左到右加入卡住的每列和
        # sortedlist记录每次加入一列后的新矩形和
        # 加入新列和后，查找之前大于等于s - k且最接近的位置即可
        for up in range(m):
            col_sum = [0] * n
            for down in range(up, m):
                # 固定上边界后，累加每列的和
                for c in range(n):
                    col_sum[c] += matrix[down][c]
                # 从左到右加入每一列，统计前c列的和到stl中
                stl = SortedList([0]) # 前缀和一开始需要补0
                tmp = 0
                for v in col_sum:
                    tmp += v
                    # 二分找sortedlist中大于等于s - k且最接近的位置
                    idx = bisect_left(stl, tmp - k)
                    # print(stl, tmp, tmp - k, idx)
                    if idx == len(stl): # 找不到符合要求的大于等于s - k的
                        pass
                    else:
                        ans = max(ans, tmp - stl[idx])
                    stl.add(tmp)
        return ans

总结

• 上下框定
• 左右前缀和，stl存前缀和
• 加到当前，找之前的
• 与顺序无关，找到第一个大于等于s - k的即可

最后

以上就是幸福台灯为你收集整理的leetcode：363. 矩形区域不超过 K 的最大数值和【上下边界框定 + 从左往右遍历 + sortedlist找最接近答案的前缀和】题目截图题目分析ac code总结的全部内容，希望文章能够帮你解决leetcode：363. 矩形区域不超过 K 的最大数值和【上下边界框定 + 从左往右遍历 + sortedlist找最接近答案的前缀和】题目截图题目分析ac code总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。