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

https://leetcode-cn.com/problems/minimum-operations-to-reduce-x-to-zero

题目描述

给你一个整数数组 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)$。

最后更新于