使数组和小于等于 x 的最少时间
难度:
标签:
题目描述
You are given two 0-indexed integer arrays nums1 and nums2 of equal length. Every second, for all indices 0 <= i < nums1.length, value of nums1[i] is incremented by nums2[i]. After this is done, you can do the following operation:
- Choose an index
0 <= i < nums1.lengthand makenums1[i] = 0.
You are also given an integer x.
Return the minimum time in which you can make the sum of all elements of nums1 to be less than or equal to x, or -1 if this is not possible.
Example 1:
Input: nums1 = [1,2,3], nums2 = [1,2,3], x = 4 Output: 3 Explanation: For the 1st second, we apply the operation on i = 0. Therefore nums1 = [0,2+2,3+3] = [0,4,6]. For the 2nd second, we apply the operation on i = 1. Therefore nums1 = [0+1,0,6+3] = [1,0,9]. For the 3rd second, we apply the operation on i = 2. Therefore nums1 = [1+1,0+2,0] = [2,2,0]. Now sum of nums1 = 4. It can be shown that these operations are optimal, so we return 3.
Example 2:
Input: nums1 = [1,2,3], nums2 = [3,3,3], x = 4 Output: -1 Explanation: It can be shown that the sum of nums1 will always be greater than x, no matter which operations are performed.
Constraints:
1 <= nums1.length <= 1031 <= nums1[i] <= 1030 <= nums2[i] <= 103nums1.length == nums2.length0 <= x <= 106
代码结果
运行时间: 220 ms, 内存: 16.3 MB
/*
思路：
1. 使用Java Stream的方式来实现。
2. 在每一秒钟后，使用stream更新 nums1 的值。
3. 通过stream计算和来检查是否 <= x。
*/
import java.util.stream.IntStream;
public class Solution {
public int minTime(int[] nums1, int[] nums2, int x) {
int n = nums1.length;
int[] sum = new int[n + 1];
for (int t = 0; t < n; t++) {
for (int i = 0; i < n; i++) {
nums1[i] += nums2[i];
}
int total = IntStream.of(nums1).sum();
if (total <= x) {
return t + 1;
}
}
return -1;
}
}解释
方法:
题解使用了动态规划的策略，首先预先判断nums1的初始和是否已经小于等于x，若是，则直接返回0秒。接着，考虑最多需要length次操作，对nums2进行降序排序，并计算出一个阈值thres。thres代表通过对所有元素设置为0后可以减少的最大可能值，若x小于该阈值，则直接返回-1表示无法实现。然后使用动态规划数组dp，其中dp[j]存储前i个元素操作j次能达到的最大减少值。遍历所有组合，并根据每次操作的累积结果和x的关系来判断所需的最小时间。
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
在题解中提到的阈值`thres`是如何计算的？能否详细解释其意义及计算过程？
▷🦆
为什么在判断`x`小于`thres`时可以直接返回`-1`？这种情况代表了什么实际的意义？
▷🦆
动态规划数组`dp`中的`dp[j]`代表什么意义？在动态规划过程中，它是如何被更新的？
▷🦆
在代码中，为什么需要对`nums2`和`nums1`的元组按降序排序？这样的排序有什么特殊目的或优势？
▷