2024.1.19力扣每日一题——使数组和小于等于 x 的最少时间

题目来源

力扣每日一题；题序：2809

我的题解

题解参考官方题解。

方法一 动态规划

若能找到一个最小的时间t使得数组和小于等于x，则最多在一轮遍历（n秒）中找到，否则就找不到。所以观察重置为零的数，会按照 nums2的速度增长，所以对于所有操作的数，我们应该优先操作增长速度慢的数。
如果我们选择多个索引$i_1,i_2,\dots ,i_k$，那么按照 $num{s}_2[i_1]\le num{s}_2[i_2]\le \dots \le num{s}_2[i_k]$的顺序进行设置是最优的。按照 nums2 的大小对所有数值对进行排序（非递减顺序）。用 dp[j][i] 表示如果对前 j个元素进行 i次操作，可以减少的最大总值，初始值为零。对于第 j 个元素，我们可以选择对其进行操作或者不操作，由此可以得到状态转移方程：
dp[j][i]=max?(dp[j?1][i],dp[j?1][i?1]+$num{s}_2$[j?1]×i+$num{s}_1$[j?1])
其中有 1≤i≤j≤n。
最后返回最小的 t，使满足 sum($num{s}_1$)+sum($num{s}_2$)×t?dp[n][t]≤x，如果不存在返回 ?1。

时间复杂度：O($n^2$)
空间复杂度：O($n^2$)。动态规划数组空间

public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {
    int n = nums1.size(), s1 = 0, s2 = 0;
    int[][] dp = new int[n + 1][n + 1];
    //这里是技巧：如何不改变原数组对其进行排序
    Integer index[]=new Integer[nums2.size()];
    for(int i=0;i< nums2.size();i++){
        index[i]=i;
    }
    Arrays.sort(index,(a,b)->nums2.get(a)-nums2.get(b));
    for (int i = 0; i < n; i++) {

        int a = nums1.get(i), b = nums2.get(i);
        s1 += a;
        s2 += b;
    }
    for (int j = 1; j <= n; ++j) {
        int in=index[j-1];
        int b = nums2.get(in), a = nums1.get(in);
        for (int i = j; i > 0; --i) {
            dp[j][i] = Math.max(dp[j - 1][i], dp[j - 1][i - 1] + i * b + a);
        }
    }
    for (int i = 0; i <= n; i++) {
        if (s2 * i + s1 - dp[n][i] <= x) {
            return i;
        }
    }
    return -1;
}

方法二 动态规划（空间优化）

dp[i] 的状态只和 dp[i?1]有关。
所以可以省去第一个维度，从而优化空间，从 O($n^2$) 优化到 O(n)，其中 n 是输入数组的长度。

时间复杂度：O($n^2$)
空间复杂度：O(n)

public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {
 	int n = nums1.size(), s1 = 0, s2 = 0;
    int[] dp = new int[n + 1];
    Integer index[]=new Integer[nums2.size()];
    for(int i=0;i< nums2.size();i++){
        index[i]=i;
    }
    Arrays.sort(index,(a,b)->nums2.get(a)-nums2.get(b));
    for (int i = 0; i < n; i++) {

        int a = nums1.get(i), b = nums2.get(i);
        s1 += a;
        s2 += b;
    }
    for (int j = 1; j <= n; ++j) {
        int in=index[j-1];
        int b = nums2.get(in), a = nums1.get(in);
        for (int i = j; i > 0; --i) {
            dp[i] = Math.max(dp[i], dp[i - 1] + i * b + a);
        }
    }
    for (int i = 0; i <= n; i++) {
        if (s2 * i + s1 - dp[i] <= x) {
            return i;
        }
    }
    return -1;
}

注意技巧：如何在不改变原数组的情况下对数组进行排序，需要额外的序号数组。

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~