(多图详解)优化枚举的基本思路 & 将二维抽象成一维 & 最大化「二分」效益 & 空间优化|Java 刷题打卡

简介: (多图详解)优化枚举的基本思路 & 将二维抽象成一维 & 最大化「二分」效益 & 空间优化|Java 刷题打卡

题目描述



这是 LeetCode 上的 363. 矩形区域不超过 K 的最大数值和 ,难度为 困难


Tag : 「二分」、「前缀和」


给你一个 m x n 的矩阵 matrix 和一个整数 k ,找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。


题目数据保证总会存在一个数值和不超过 k 的矩形区域。

 

示例 1:


输入:matrix = [[1,0,1],[0,-2,3]], k = 2
输出:2
解释:蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2,且 2 是不超过 k 的最大数字(k = 2)。
复制代码


示例 2:


输入:matrix = [[2,2,-1]], k = 3
输出:3
复制代码


提示:


  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -100 <= matrix[i][j] <= 100
  • -10510^5105 <= k <= 10510^5105


朴素二维前缀和



从题面来看显然是一道「二维前缀和」的题目,如果你还不了解「二维前缀和」,可以看看 (题解)304. 二维区域和检索 - 矩阵不可变。本题预处理前缀和的复杂度为 O(m∗n)O(m * n)O(mn)


搜索所有子矩阵需要枚举「矩形左上角」和「矩形右下角」,复杂度是 O(m2∗n2)O(m^2 * n^2)O(m2n2)


因此,如果把本题当做二维前缀和模板题来做的话,整体复杂度是 O(m2∗n2)O(m^2 * n^2)O(m2n2)


数据范围是 10210^2102,对应的计算量是 10810^8108,理论上会超时,但当我们枚举「矩形左上角」(i,j)(i,j)(i,j) 的时候,我们只需要搜索位于 (i,j)(i,j)(i,j) 的右下方的点 (p,q)(p,q)(p,q) 作为「矩形右下角」,所以其实我们是取不满 m2∗n2m^2 * n^2m2n2 的,但仍然具有超时风险(2021/04/20 Java 测试可通过,C++ 使用 vector 会 TLE)。


代码:


class Solution {
    public int maxSumSubmatrix(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        int[][] sum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        int ans = Integer.MIN_VALUE;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int p = i; p <= m; p++) {
                    for (int q = j; q <= n; q++) {
                        int cur = sum[p][q] - sum[i - 1][q] - sum[p][j - 1] + sum[i - 1][j - 1];
                        if (cur <= k) {
                            ans = Math.max(ans, cur);
                        } 
                    }
                }
            }
        }
        return ans;
    }
}
复制代码


  • 时间复杂度:预处理前缀和数组复杂度为 O(m∗n)O(m * n)O(mn),查找答案的复杂度为 O(m2∗n2)O(m^2 * n^2)O(m2n2)。整体复杂度为 O(m2∗n2)O(m^2 * n^2)O(m2n2)
  • 空间复杂度:O(m∗n)O(m * n)O(mn)


前缀和 & 二分(抽象一维)



我们来细想一下「朴素二维前缀和」解法是如何搜索答案(子矩阵):通过枚举「左上角」&「右下角」来唯一确定某个矩阵


换句话说是通过枚举 (i,j)(i,j)(i,j)(p,q)(p,q)(p,q) 来唯一确定子矩阵的四条边,每个坐标点可以看作确定子矩阵的某条边。


既然要确定的边有四条,我们可以如何降低复杂度呢?


简单的,我们先思考一下同样是枚举的 1. 两数之和 问题。


1. 两数之和 中可以暴力枚举两个数,也可以只枚举其中一个数,然后使用数据结构(哈希表)来加速找另一个数(这是一个通用的「降低枚举复杂度」思考方向)。


对应到本题,我们可以枚举其中三条边,然后使用数据结构来加速找第四条边。


当我们确定了三条边(红色)之后,形成的子矩阵就单纯取决于第四条边的位置(黄色):


网络异常,图片无法展示
|


于是问题转化为「如何快速求得第四条边(黄色)的位置在哪」。


我们可以进一步将问题缩小,考虑矩阵只有一行(一维)的情况:


网络异常,图片无法展示
|


这时候问题进一步转化为「在一维数组中,求解和不超过 K 的最大连续子数组之和」。


对于这个一维问题,我们可以先预处理出「前缀和」,然后枚举子数组的左端点,然后通过「二分」来求解其右端点的位置。


假定我们已经求得一维数组的前缀和数组 sum,即可得下标范围 [i,j][i,j][i,j] 的和为:

areaSum(i,j)=sum[j]−sum[i−1]⩽kareaSum(i, j) = sum[j] - sum[i - 1] \leqslant kareaSum(i,j)=sum[j]sum[i1]k


经过变形后得:


sum[j]⩽k+sum[i−1]sum[j] \leqslant k + sum[i - 1]sum[j]k+sum[i1]

我们有两种思路来最大化 areaSum(i,j)areaSum(i, j)areaSum(i,j)


  • 确定(枚举)左端点位置 i,求得符合条件的最大右端点 sum[j]
  • 确定(枚举)右端点位置 j,求得符合条件的最小左端点 sum[i]


对于没有负权值的一维数组,我们可以枚举左端点 i,同时利用前缀和的「单调递增」特性,通过「二分」找到符合 sum[j]⩽k+sum[i−1]sum[j] \leqslant k + sum[i - 1]sum[j]k+sum[i1] 条件的最大值 sum[j],从而求解出答案。


但是如果是含有负权值的话,前缀和将会丢失「单调递增」的特性,我们也就无法使用枚举 i 并结合「二分」查找 j 的做法。


这时候需要将过程反过来处理:我们从左到右枚举 j,并使用「有序集合」结构维护遍历过的位置,找到符合 sum[j]−k⩽sum[i]sum[j] - k \leqslant sum[i]sum[j]ksum[i] 条件的最小值 sum[i],从而求解出答案。


基于上述分析,解决这样的一维数组问题复杂度是 O(nlog⁡n)O(n\log{n})O(nlogn) 的。

将这样的思路应用到二维需要一点点抽象能力。


同时,将一维思路应用到本题(二维),复杂度要么是 O(m2∗nlog⁡n)O(m^2 * n\log{n})O(m2nlogn) 要么是 O(n2∗mlog⁡m)O(n^2 * m\log{m})O(n2mlogm)


我们先不考虑「最大化二分收益」问题,先假设我们是固定枚举「上下行」和「右边列」,这时候唯一能够确定一个子矩阵则是取决于「左边列」:


网络异常,图片无法展示
|


重点是如何与「一维」问题进行关联:显然「目标子矩阵的和」等于「子矩阵的右边列 与 原矩阵的左边列 形成的子矩阵和」-「子矩阵左边列 与 原矩阵左边列 形成的子矩阵和」


我们可以使用 area[r] 代表「子矩阵的右边列 与 原矩阵的左边列 形成的子矩阵和」,使用 area[l - 1] 代表「子矩阵的左边列 与 原矩阵的左边列 形成的子矩阵和」的话,则有:


target=area[r]−area[l−1]⩽ktarget = area[r] - area[l - 1] \leqslant ktarget=area[r]area[l1]k


这与我们「一维问题」完全一致,同时由「上下行」&「右边列」可以直接确定 area[r] 的大小,通过「有序集合」存储我们遍历 r 过程中的所有的 area[r] 从而实现「二分」查找符合 area[r]−k⩽area[l−1]area[r] - k \leqslant area[l - 1]area[r]karea[l1] 条件的 最小area[l - 1]


至此,我们通过预处理前缀和 + 容斥原理彻底将题目转化为「一维问题」进行来求解。

代码:


class Solution {
    public int maxSumSubmatrix(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        // 预处理前缀和
        int[][] sum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        int ans = Integer.MIN_VALUE;
        // 遍历子矩阵的上边界
        for (int top = 1; top <= m; top++) {
            // 遍历子矩阵的下边界
            for (int bot = top; bot <= m; bot++) {
                // 使用「有序集合」维护所有遍历到的右边界
                TreeSet<Integer> ts = new TreeSet<>();
                ts.add(0);
                // 遍历子矩阵的右边界
                for (int r = 1; r <= n; r++) {
                    // 通过前缀和计算 right
                    int right = sum[bot][r] - sum[top - 1][r];
                    // 通过二分找 left
                    Integer left = ts.ceiling(right - k);
                    if (left != null) {
                        int cur = right - left;
                        ans = Math.max(ans, cur);
                    }
                    // 将遍历过的 right 加到有序集合
                    ts.add(right);
                }
            }
        }
        return ans;
    }
}
复制代码


  • 时间复杂度:枚举上下边界复杂度为 O(m2)O(m^2)O(m2);枚举右边界为 O(n)O(n)O(n),使用 TreeSet(基于红黑树)存储和查找左边界复杂度为 O(log⁡n)O(\log{n})O(logn)。整体复杂度为 O(m2∗nlog⁡n)O(m^2 * n\log{n})O(m2nlogn)
  • 空间复杂度:O(m∗n)O(m * n)O(mn)


最大化「二分」效益



上述解法中,我们先枚举的是「上下行」和「右边列」,然后通过 TreeSet 来「二分」出符合条件的「左边列」。


事实上,我们需要将「二分过程」应用到数值较大的行或者列之中,这样才能最大化我们查找的效率(同时也回答了本题的进阶部分)。


代码:


class Solution {
    public int maxSumSubmatrix(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        int[][] sum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        // 固定的是否为右边界
        boolean isRight = n > m;
        int ans = Integer.MIN_VALUE;
        for (int i = 1; i <= (isRight ? m : n); i++) {
            for (int j = i; j <= (isRight ? m : n); j++) {
                TreeSet<Integer> ts = new TreeSet<>();
                ts.add(0);
                for (int fixed = 1; fixed <= (isRight ? n : m); fixed++) {
                    int a = isRight ? sum[j][fixed] - sum[i - 1][fixed] : sum[fixed][j] - sum[fixed][i - 1];
                    Integer b = ts.ceiling(a - k);
                    if (b != null) {
                        int cur = a - b;
                        ans = Math.max(ans, cur);
                    }
                    ts.add(a);
                }
            }
        }
        return ans;
    }
}
复制代码


  • 时间复杂度:预处理「每行」或「每列」的前缀和,复杂度为 O(m∗n)O(m * n)O(mn);枚举子矩阵的「上下行」或「左右行」,复杂度为 O(min⁡(m,n)2)O(\min(m, n)^2)O(min(m,n)2);结合二维前缀和套用一维最大连续子数组解决方案,复杂度为max⁡(m,n)log⁡max⁡(m,n)\max(m, n)\log{\max(m, n)}max(m,n)logmax(m,n)。整体复杂度为 O(min⁡(m,n)2∗max⁡(m,n)log⁡max⁡(m,n))O(\min(m, n)^2 * \max(m, n)\log{\max(m, n)})O(min(m,n)2max(m,n)logmax(m,n))
  • 空间复杂度:O(m∗n)O(m * n)O(mn)


空间优化



不难发现,我们在原矩阵搜索目标子矩阵的过程是严格的「从上到下」&「从左到右」的。


因此我们可以将计算前缀和的逻辑下放到搜索子矩阵的循环里去做,从而将 O(m∗n)O(m * n)O(mn) 的空间复杂度下降到 O(max⁡(m,n))O(\max(m,n))O(max(m,n))


代码:


class Solution {
    public int maxSumSubmatrix(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        boolean isRight = n > m;
        int[] sum = isRight ? new int[n + 1] : new int[m + 1];
        int ans = Integer.MIN_VALUE;
        for (int i = 1; i <= (isRight ? m : n); i++) {
            Arrays.fill(sum, 0);
            for (int j = i; j <= (isRight ? m : n); j++) {
                TreeSet<Integer> ts = new TreeSet<>();
                ts.add(0);
                int a = 0;
                for (int fixed = 1; fixed <= (isRight ? n : m); fixed++) {
                    sum[fixed] += isRight ? mat[j - 1][fixed - 1] : mat[fixed - 1][j - 1] ;
                    a += sum[fixed];
                    Integer b = ts.ceiling(a - k);
                    if (b != null) {
                        int cur = a - b;
                        ans = Math.max(ans, cur);
                    }
                    ts.add(a);
                }
            }
        }
        return ans;
    }
}
复制代码


  • 时间复杂度:预处理「每行」或「每列」的前缀和,复杂度为 O(m∗n)O(m * n)O(mn);枚举子矩阵的「上下行」或「左右行」,复杂度为 O(min⁡(m,n)2)O(\min(m, n)^2)O(min(m,n)2);结合二维前缀和套用一维最大连续子数组解决方案,复杂度为max⁡(m,n)log⁡max(m,n)\max(m, n)\log{max(m, n)}max(m,n)logmax(m,n)。整体复杂度为 O(min⁡(m,n)2∗max⁡(m,n)log⁡max⁡(m,n))O(\min(m, n)^2 * \max(m, n)\log{\max(m, n)})O(min(m,n)2max(m,n)logmax(m,n))
  • 空间复杂度:O(max⁡(m,n))O(\max(m, n))O(max(m,n))


最后



这道困难题还是有点难度的,掘友们学会了吗 🤣


建议着重体会「抽象一维」的如何被推导出来了的 ~

相关文章
|
23天前
|
监控 算法 Java
Java虚拟机(JVM)垃圾回收机制深度剖析与优化策略####
本文作为一篇技术性文章,深入探讨了Java虚拟机(JVM)中垃圾回收的工作原理,详细分析了标记-清除、复制算法、标记-压缩及分代收集等主流垃圾回收算法的特点和适用场景。通过实际案例,展示了不同GC(Garbage Collector)算法在应用中的表现差异,并针对大型应用提出了一系列优化策略,包括选择合适的GC算法、调整堆内存大小、并行与并发GC调优等,旨在帮助开发者更好地理解和优化Java应用的性能。 ####
29 0
|
1天前
|
缓存 算法 搜索推荐
Java中的算法优化与复杂度分析
在Java开发中,理解和优化算法的时间复杂度和空间复杂度是提升程序性能的关键。通过合理选择数据结构、避免重复计算、应用分治法等策略,可以显著提高算法效率。在实际开发中,应该根据具体需求和场景,选择合适的优化方法,从而编写出高效、可靠的代码。
15 6
|
23天前
|
存储 监控 小程序
Java中的线程池优化实践####
本文深入探讨了Java中线程池的工作原理,分析了常见的线程池类型及其适用场景,并通过实际案例展示了如何根据应用需求进行线程池的优化配置。文章首先介绍了线程池的基本概念和核心参数,随后详细阐述了几种常见的线程池实现(如FixedThreadPool、CachedThreadPool、ScheduledThreadPool等)的特点及使用场景。接着,通过一个电商系统订单处理的实际案例,分析了线程池参数设置不当导致的性能问题,并提出了相应的优化策略。最终,总结了线程池优化的最佳实践,旨在帮助开发者更好地利用Java线程池提升应用性能和稳定性。 ####
|
15天前
|
存储 Java
Java 11 的String是如何优化存储的?
本文介绍了Java中字符串存储优化的原理和实现。通过判断字符串是否全为拉丁字符,使用`byte`代替`char`存储,以节省空间。具体实现涉及`compress`和`toBytes`方法,前者用于尝试压缩字符串,后者则按常规方式存储。代码示例展示了如何根据配置决定使用哪种存储方式。
|
24天前
|
存储 算法 Java
Java 内存管理与优化:掌控堆与栈,雕琢高效代码
Java内存管理与优化是提升程序性能的关键。掌握堆与栈的运作机制,学习如何有效管理内存资源,雕琢出更加高效的代码,是每个Java开发者必备的技能。
49 5
|
22天前
|
存储 监控 算法
Java虚拟机(JVM)垃圾回收机制深度解析与优化策略####
本文旨在深入探讨Java虚拟机(JVM)的垃圾回收机制,揭示其工作原理、常见算法及参数调优方法。通过剖析垃圾回收的生命周期、内存区域划分以及GC日志分析,为开发者提供一套实用的JVM垃圾回收优化指南,助力提升Java应用的性能与稳定性。 ####
|
25天前
|
存储 缓存 安全
Java 集合框架优化:从基础到高级应用
《Java集合框架优化:从基础到高级应用》深入解析Java集合框架的核心原理与优化技巧,涵盖列表、集合、映射等常用数据结构,结合实际案例,指导开发者高效使用和优化Java集合。
35 4
|
2天前
|
安全 Java Kotlin
Java多线程——synchronized、volatile 保障可见性
Java多线程中,`synchronized` 和 `volatile` 关键字用于保障可见性。`synchronized` 保证原子性、可见性和有序性,通过锁机制确保线程安全;`volatile` 仅保证可见性和有序性,不保证原子性。代码示例展示了如何使用 `synchronized` 和 `volatile` 解决主线程无法感知子线程修改共享变量的问题。总结:`volatile` 确保不同线程对共享变量操作的可见性,使一个线程修改后,其他线程能立即看到最新值。
|
2天前
|
消息中间件 缓存 安全
Java多线程是什么
Java多线程简介:本文介绍了Java中常见的线程池类型,包括`newCachedThreadPool`(适用于短期异步任务)、`newFixedThreadPool`(适用于固定数量的长期任务)、`newScheduledThreadPool`(支持定时和周期性任务)以及`newSingleThreadExecutor`(保证任务顺序执行)。同时,文章还讲解了Java中的锁机制,如`synchronized`关键字、CAS操作及其实现方式,并详细描述了可重入锁`ReentrantLock`和读写锁`ReadWriteLock`的工作原理与应用场景。
|
2天前
|
安全 Java 编译器
深入理解Java中synchronized三种使用方式:助您写出线程安全的代码
`synchronized` 是 Java 中的关键字,用于实现线程同步,确保多个线程互斥访问共享资源。它通过内置的监视器锁机制,防止多个线程同时执行被 `synchronized` 修饰的方法或代码块。`synchronized` 可以修饰非静态方法、静态方法和代码块,分别锁定实例对象、类对象或指定的对象。其底层原理基于 JVM 的指令和对象的监视器,JDK 1.6 后引入了偏向锁、轻量级锁等优化措施,提高了性能。
12 3