LeetCode 题解工作台
使数组和小于等于 x 的最少时间
给你两个长度相等下标从 0 开始的整数数组 nums1 和 nums2 。每一秒，对于所有下标 0 ， nums1[i] 的值都增加 nums2[i] 。操作 完成后 ，你可以进行如下操作： 选择任一满足 0 的下标 i ，并使 nums1[i] = 0 。 同时给你一个整数 x 。 请你返回使 n…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们注意到，如果我们多次操作同一个数，那么只有最后一次操作是有意义的，其余的对该数的操作，只会使得其它数字增大。因此，我们最多对每个数操作一次，也即是说，操作次数在 之间。 我们不妨假设进行了 次操作，操作的数字下标分别为 $i_1, i_2, \cdots, i_j$，那么对于这 次操作，每一次可以使得数组元素和减少的值为：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你两个长度相等下标从 0 开始的整数数组 nums1 和 nums2 。每一秒，对于所有下标 0 <= i < nums1.length ，nums1[i] 的值都增加 nums2[i] 。操作 完成后 ，你可以进行如下操作：
- 选择任一满足
0 <= i < nums1.length的下标i，并使nums1[i] = 0。
同时给你一个整数 x 。
请你返回使 nums1 中所有元素之和 小于等于 x 所需要的 最少 时间，如果无法实现，那么返回 -1 。
示例 1：
输入：nums1 = [1,2,3], nums2 = [1,2,3], x = 4 输出：3 解释： 第 1 秒，我们对 i = 0 进行操作，得到 nums1 = [0,2+2,3+3] = [0,4,6] 。 第 2 秒，我们对 i = 1 进行操作，得到 nums1 = [0+1,0,6+3] = [1,0,9] 。 第 3 秒，我们对 i = 2 进行操作，得到 nums1 = [1+1,0+2,0] = [2,2,0] 。 现在 nums1 的和为 4 。不存在更少次数的操作，所以我们返回 3 。
示例 2：
输入：nums1 = [1,2,3], nums2 = [3,3,3], x = 4 输出：-1 解释：不管如何操作，nums1 的和总是会超过 x 。
提示：
1 <= nums1.length <= 1031 <= nums1[i] <= 1030 <= nums2[i] <= 103nums1.length == nums2.length0 <= x <= 106
解题思路
方法一：排序 + 动态规划
我们注意到，如果我们多次操作同一个数，那么只有最后一次操作是有意义的，其余的对该数的操作，只会使得其它数字增大。因此，我们最多对每个数操作一次，也即是说，操作次数在 之间。
我们不妨假设进行了 次操作，操作的数字下标分别为 ，那么对于这 次操作，每一次可以使得数组元素和减少的值为：
从贪心的角度考虑，为了使得数组元素和的减少量最大，我们应当让 中的较大元素尽可能放在后面操作。因此，我们可以对 和 按照 的元素值从小到大进行排序。
接下来，我们考虑动态规划的实现。我们用 表示对于数组 的前 个元素，进行 次操作，所能减少的数组元素和的最大值。我们可以得到如下的状态转移方程：
最后，我们枚举 ，找到最小的满足 的 即可。
时间复杂度 ，空间复杂度 。其中 是数组的长度。
class Solution:
def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:
n = len(nums1)
f = [[0] * (n + 1) for _ in range(n + 1)]
for i, (a, b) in enumerate(sorted(zip(nums1, nums2), key=lambda z: z[1]), 1):
for j in range(n + 1):
f[i][j] = f[i - 1][j]
if j > 0:
f[i][j] = max(f[i][j], f[i - 1][j - 1] + a + b * j)
s1 = sum(nums1)
s2 = sum(nums2)
for j in range(n + 1):
if s1 + s2 * j - f[n][j] <= x:
return j
return -1
我们注意到，状态 只与 和 有关，因此我们可以优化掉第一维，将空间复杂度降低到 。
class Solution:
def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:
n = len(nums1)
f = [0] * (n + 1)
for a, b in sorted(zip(nums1, nums2), key=lambda z: z[1]):
for j in range(n, 0, -1):
f[j] = max(f[j], f[j - 1] + a + b * j)
s1 = sum(nums1)
s2 = sum(nums2)
for j in range(n + 1):
if s1 + s2 * j - f[j] <= x:
return j
return -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depend on DP table size and how the state transitions are implemented. Sorting adds O(n log n) overhead, while DP can approach O(n * maxTime) depending on the maximum sum and resets allowed. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Consider the optimality of resetting each index only once.
- question_mark
Think about how state transitions affect future sums for the DP table.
- question_mark
Be ready to justify why certain orders of resets minimize total time.
常见陷阱
外企场景- error
Resetting an index multiple times, violating the one-time rule.
- error
Ignoring the growth from nums2 increments in future seconds.
- error
Failing to return -1 when no valid sequence achieves sum <= x.
进阶变体
外企场景- arrow_right_alt
Change the problem to allow multiple resets per index, requiring a more complex DP state.
- arrow_right_alt
Introduce negative nums2 increments, affecting which indices to reset.
- arrow_right_alt
Ask for maximum sum reduction instead of minimum time, adjusting optimization criteria.