【LeetCode 1695. 删除子数组的最大得分】解析-EW帮帮网

LeetCode中国站原文

https://leetcode.cn/problems/maximum-erasure-value/

原始题目

题目描述

给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的得分就是子数组各元素之和。

返回只删除一个子数组可获得的 最大得分 。

如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。

示例 1：

输入：nums = [4,2,4,5,6]
输出：17
解释：最优子数组是 ，得分为 2 + 4 + 5 + 6 = 17 。

示例 2：

输入：nums = [5,2,1,2,5,2,1,2,5]
输出：8
解释：最优子数组是[5,2,1] 或 [1,2,5] ，得分为 5 + 2 + 1 = 8 。

提示：

$1 <= nums.length <= 10^5$
$1 <= nums[i] <= 10^4$

讲解

滑动窗口的艺术：寻找无与伦比的“纯净”子数组

大家好！今天我们要攻略的是一道非常经典的算法题——LeetCode 1695. 删除子数组的最大得分。这道题的题面可能会让人有点困惑，但它的本质，是要求我们找到一个元素各不相同的连续子数组，并让这个子数组的和最大。

这道题是“滑动窗口”算法的完美应用场景，通过它，我们可以深刻理解滑动窗口如何巧妙地将一个看似需要 O(N^2) 暴力求解的问题，优化到 O(N) 的线性时间复杂度。

第一部分：算法思想 —— 可伸缩的“探索边界”

1. 问题的核心：找到最“值钱”的“纯净”片段

想象一下，nums 数组是一条埋藏着金矿的矿脉。每一段矿石（数字）都有一个价值（数值大小）。我们的任务是，在这条矿脉中，找到一段连续的、且内部没有重复种类矿石的“纯净矿段”，并要求这段矿石的总价值最高。

上图中，[4,2] 是一个纯净矿段，总价值6。当我们想把下一个 4 也包含进来时，就发现矿石种类重复了。为了保持“纯净”，我们必须做出取舍。最优的策略是，把第一次出现的 4 以及它之前的所有矿石都丢掉，形成一个新的、从 2 开始的纯净矿段 [2,4,5,6]，总价值17。

2. 滑动窗口：一个能屈能伸的“探索框”

如何系统性地找出所有这样的“纯净矿段”并比较它们的价值呢？暴力枚举所有子数组会非常慢。这时，滑动窗口就闪亮登场了。

我们可以把“滑动窗口”想象成一个架在矿脉上的、左右边界可以自由伸缩的“探索框”。

right 指针：代表探索框的右边界，它总是勇往直前，不断地尝试将新的矿石纳入框中。
left 指针：代表探索框的左边界，它比较保守，只有在框内出现问题（发现重复矿石）时，才不情愿地向前挪动，把框最左边的矿石丢出去，以解决问题。

“探索框”的工作流程：

扩张：right 指针向右移动，将一个新矿石 nums[right] “框”进来。同时，我们累加当前框内所有矿石的总价值。
检查：检查新框进来的 nums[right] 是否与框内已有的矿石重复了。
收缩（如果需要）：如果发现重复，left 指针就必须向右移动，把框最左边的矿石 nums[left] 一个个地丢出去，并从总价值中减去它们的价值。这个过程一直持续，直到框内不再有重复的 nums[right] 为止。
记录：在每一次扩张和收缩之后，我们的“探索框”内都是一个“纯净矿段”。我们在此刻计算框内的总价值，并用它来挑战我们已知的“最大价值记录”。
循环：right 指针继续向右移动，重复上述过程，直到探索完整个矿脉。

这个过程保证了我们能不遗漏地检查所有以 right 指针为结尾的、最长的“纯净矿段”，并找到其中的价值最大者。

第二部分：代码实现 —— 滑动窗口的“装备”

要实现滑动窗口，我们还需要一些“装备”来辅助我们的 left 和 right 指针。

一个账本（哈希集合 Set）：用来快速查询“探索框”内是否已经存在某种矿石。Set 提供了 O(1) 复杂度的添加和查询操作，非常适合这个场景。
一个计算器（currentSum变量）：实时记录当前“探索框”内所有矿石的总价值。
一个记录板（maxSum变量）：记录我们探索至今，发现的最高价值。

完整代码展示

class Solution {
    /**
     * 找到元素各不相同的连续子数组的最大和。
     * @param nums 正整数数组
     * @return 最大得分
     */
    public int maximumUniqueSubarray(int[] nums) {
        // 滑动窗口的左边界
        int left = 0;
        
        // 记录全局最大得分
        long maxSum = 0;
        // 记录当前窗口内的得分
        long currentSum = 0;
        
        // “账本”，用于快速检查窗口内元素是否重复
        Set<Integer> windowSet = new HashSet<>();

        // right 指针负责探索，遍历整个数组
        for (int right = 0; right < nums.length; right++) {
            int numToAdd = nums[right];

            // 收缩步骤：
            // 如果“账本”里已经有新来的元素，说明窗口需要收缩。
            // while 循环确保我们一直收缩，直到重复元素被从左边移出窗口。
            while (windowSet.contains(numToAdd)) {
                int numToRemove = nums[left];
                
                // 从“账本”中移除最左边的元素
                windowSet.remove(numToRemove);
                // 从当前和中减去它的值
                currentSum -= numToRemove;
                // 左指针向右移动
                left++;
            }

            // 扩张步骤：
            // 将新元素加入窗口
            windowSet.add(numToAdd);
            currentSum += numToAdd;
            
            // 记录步骤：
            // 在每次窗口稳定后（即不包含重复元素），更新最大得分
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return (int)maxSum;
    }
}

代码精讲

数据类型：虽然题目提示中的数值不大，但 nums.length 和 nums[i] 的乘积可能超过 int 的最大值，所以使用 long 来存储和（maxSum, currentSum）是一个非常好的编程习惯，可以避免潜在的整数溢出问题。
while 循环收缩：使用 while 而不是 if 来收缩窗口至关重要。因为可能存在 [1, 2, 3, 1, 2] 这样的情况，当 right 指向第二个 2 时，left 需要连续收缩两次（移出1和旧的2），才能保证窗口的纯净。
时间复杂度：虽然代码里有 for 循环嵌套 while 循环，但仔细观察可以发现，left 和 right 指针都只会从头到尾各自移动一次，绝不后退。因此，每个元素最多被访问两次（一次被right加入，一次被left移除）。所以总的时间复杂度是 O(N)，而不是 O(N^2)。

【LeetCode 1695. 删除子数组的最大得分】解析

目录