LeetCode 1658. 将 x 减到 0 的最小操作数

Question

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1
示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

提示：

1 <= nums.length <= 10^5
1 <= nums[i] <= 104
1 <= x <= 109

前置知识

• 堆
• 滑动窗口

堆

思路

这里可以使用堆来解决。具体来说是我自己总结的多路归并题型。

代码

代码支持：Python3

Python3 Code:

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        # 看数据范围，这种方法铁定超时（指数复杂度）
        h = [(0, 0, len(nums) - 1, x)]
        while h:
            moves,l,r,remain = heapq.heappop(h)
            if remain == 0: return moves
            if l + 1 < len(nums): heapq.heappush(h, (moves + 1, l + 1,r, remain-nums[l]))
            if r > 0: heapq.heappush(h, (moves + 1, l,r-1, remain-nums[r]))
        return -1

复杂度分析

• 时间复杂度：$O(2^moves)$，其中 moves 为题目答案。最坏情况 moves 和 N 同阶，也就是 $2^N$。
• 空间复杂度：$O(1)$。

由于题目数组长度最大可以达到 10^5， 这提示我们此方法必然超时。

我们必须考虑时间复杂度更加优秀的方式。

动态规划（记忆化递归）

思路

由上面的解法， 我们不难想到使用动态规划来解决。

枚举所有的 l,r,x 组合，并找到最小的，其中 l 表示 左指针， r 表示右指针，x 表示剩余的数字。这里为了书写简单我使用了记忆化递归。

代码

代码支持：Python3

Python3 Code:

Python 的 @lru_cache 是缓存计算结果的数据结构， None 表示不限制容量。

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        n = len(nums)

        @lru_cache(None)
        def dp(l, r, x):
            if x == 0:
                return 0
            if x < 0 or r < 0 or l > len(nums) - 1:
                return n + 1
            return 1 + min(dp(l + 1, r, x - nums[l]), dp(l, r - 1, x - nums[r]))

        ans = dp(0, len(nums) - 1, x)
        return -1 if ans > n else ans

复杂度分析

• 时间复杂度：$O(N^2 * h)$，其中 N 为数组长度, h 为 x 的减少速度，最坏的情况可以达到三次方的复杂度。
• 空间复杂度：$O(N)$，其中 N 为数组长度，这里的空间指的是递归栈的开销。

这种复杂度仍然无法通过 10^5 规模，需要继续优化算法。

滑动窗口

思路

实际上，我们也可以逆向思考。即：我们剩下的数组一定是原数组的中间部分。

那是不是就是说，我们只要知道数据中子序和等于 sum(nums) - x 的长度。用 nums 的长度减去它就好了？

由于我们的目标是 最小操作数，因此我们只要求和为定值的最长子序列，这是一个典型的滑动窗口问题。

代码

代码支持：Python3

Python3 Code:

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        # 逆向求解，滑动窗口
        i = 0
        target = sum(nums) - x
        win = 0
        ans = len(nums)
        if target == 0: return ans
        for j in range(len(nums)):
            win += nums[j]
            while i < j and win > target:
                win -= nums[i]
                i += 1
            if win == target:
                ans = min(ans, len(nums) - (j - i + 1))
        return -1 if ans == len(nums) else ans

复杂度分析

• 时间复杂度：$O(N)$，其中 N 为数组长度。
• 空间复杂度：$O(1)$。