leetcode
leetcode 1501 ~ 1550
删除子数组的最大得分

删除子数组的最大得分

难度:

标签:

题目描述

代码结果

运行时间: 201 ms, 内存: 27.3 MB


/*
 * 题目思路:
 * 使用Java Stream和普通的集合操作实现同样的逻辑。
 * 虽然Stream不是最合适的工具,但可以通过组合Stream操作来实现。
 */

import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;

public class SolutionStream {
    public int maximumUniqueSubarray(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int[] maxScore = {0};
        int[] currentSum = {0};
        int[] left = {0};
        IntStream.range(0, nums.length).forEach(right -> {
            while (set.contains(nums[right])) {
                set.remove(nums[left[0]]);
                currentSum[0] -= nums[left[0]];
                left[0]++;
            }
            set.add(nums[right]);
            currentSum[0] += nums[right];
            maxScore[0] = Math.max(maxScore[0], currentSum[0]);
        });
        return maxScore[0];
    }
}

解释

方法:

此题解采用滑动窗口加上哈希表的方法来解决问题。首先通过计算前缀和数组来快速求出任何子数组的和。然后,使用一个哈希表来记录每个元素最后出现的位置。通过遍历数组,利用哈希表来判断当前元素是否已在当前考虑的子数组中出现过。如果出现过,说明当前子数组中已包含重复元素,需要调整滑动窗口的起始位置到重复元素的下一个位置。每次调整后,计算并更新可能的最大子数组和。最后,需要处理边界情况,即当数组遍历完成后,检查最后一个可能的子数组的得分。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在算法实现中,为什么需要使用前缀和数组来快速获取子数组的和?
前缀和数组是一种高效计算子数组和的方法。通过构造一个数组,其中每个元素表示从数组开始到当前位置的元素总和,可以快速计算任意子数组的和。具体来说,子数组从索引i到j的和可以通过pre_num[j+1] - pre_num[i]来得到,这样只需要O(1)的时间复杂度,大大提高了效率,尤其是在需要频繁计算子数组和的情况下非常有用。
🦆
哈希表中存储元素最后出现的位置是如何帮助调整滑动窗口的起始位置的?
在滑动窗口算法中,哈希表用于记录每个元素最后一次出现的位置。当遍历到数组中的某个元素时,可以快速检查该元素是否已经在当前考虑的子数组中出现过。如果已出现,并且出现的位置在当前滑动窗口的起始位置之后,这表明需要调整窗口以排除重复元素。这时,滑动窗口的起始位置更新为该重复元素上一次出现位置的下一个位置,从而保证窗口中的元素都是唯一的。
🦆
如果当前元素在哈希表中的记录位置小于当前滑动窗口的起始位置会怎样处理?
如果当前元素在哈希表中的记录位置小于滑动窗口的起始位置,这意味着这个记录的位置已不在当前考虑的子数组中。因此,这种情况下无需调整滑动窗口的起始位置,可以直接更新哈希表中该元素的位置为当前索引,继续向前遍历数组。这样做确保了哈希表总是反映每个元素最近的位置,而不会错误地引起不必要的窗口调整。
🦆
算法中如何确保每一次调整滑动窗口后都能得到一个无重复元素的子数组?
每次当检测到当前元素已存在于当前子数组中时,算法会将滑动窗口的起始位置调整到该重复元素上次出现位置的下一个位置。这种调整方式确保了所有在新起始位置之前的元素都不会包含在新的窗口中,从而移除了重复元素。通过这种方法,每次调整后的滑动窗口都只包含唯一的元素,保证了子数组的独特性。

相关问题