将数组分成最小总代价的子数组 II

You are given a 0-indexed array of integers nums of length n, and two positive integers k and dist.

The cost of an array is the value of its first element. For example, the cost of [1,2,3] is 1 while the cost of [3,4,1] is 3.

You need to divide nums into k disjoint contiguous subarrays, such that the difference between the starting index of the second subarray and the starting index of the kth subarray should be less than or equal to dist. In other words, if you divide nums into the subarrays nums[0..(i1 - 1)], nums[i1..(i2 - 1)], ..., nums[ik-1..(n - 1)], then ik-1 - i1 <= dist.

Return the minimum possible sum of the cost of these subarrays.

 

Example 1:

Input: nums = [1,3,2,6,4,2], k = 3, dist = 3
Output: 5
Explanation: The best possible way to divide nums into 3 subarrays is: [1,3], [2,6,4], and [2]. This choice is valid because ik-1 - i1 is 5 - 2 = 3 which is equal to dist. The total cost is nums[0] + nums[2] + nums[5] which is 1 + 2 + 2 = 5.
It can be shown that there is no possible way to divide nums into 3 subarrays at a cost lower than 5.

Example 2:

Input: nums = [10,1,2,2,2,1], k = 4, dist = 3
Output: 15
Explanation: The best possible way to divide nums into 4 subarrays is: [10], [1], [2], and [2,2,1]. This choice is valid because ik-1 - i1 is 3 - 1 = 2 which is less than dist. The total cost is nums[0] + nums[1] + nums[2] + nums[3] which is 10 + 1 + 2 + 2 = 15.
The division [10], [1], [2,2,2], and [1] is not valid, because the difference between ik-1 and i1 is 5 - 1 = 4, which is greater than dist.
It can be shown that there is no possible way to divide nums into 4 subarrays at a cost lower than 15.

Example 3:

Input: nums = [10,8,18,9], k = 3, dist = 1
Output: 36
Explanation: The best possible way to divide nums into 4 subarrays is: [10], [8], and [18,9]. This choice is valid because ik-1 - i1 is 2 - 1 = 1 which is equal to dist.The total cost is nums[0] + nums[1] + nums[2] which is 10 + 8 + 18 = 36.
The division [10], [8,18], and [9] is not valid, because the difference between ik-1 and i1 is 3 - 1 = 2, which is greater than dist.
It can be shown that there is no possible way to divide nums into 3 subarrays at a cost lower than 36.

 

Constraints:

• 3 <= n <= 105
• 1 <= nums[i] <= 109
• 3 <= k <= n
• k - 2 <= dist <= n - 2

/*
 * 思路：
 * 1. 使用 Java Stream API 重构动态规划方法。
 * 2. dp[i][j] 表示将前 i 个元素分成 j 段的最小总代价。
 * 3. 我们需要考虑最后一段的起点，并保证其起点与第一段的起点距离不超过 dist。
 */

import java.util.Arrays;
import java.util.stream.IntStream;

public class Solution {
    public int minCost(int[] nums, int k, int dist) {
        int n = nums.length;
        int[][] dp = new int[n + 1][k + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][0] = 0;
        IntStream.range(1, n + 1).forEach(i -> {
            IntStream.range(1, k + 1).forEach(j -> {
                IntStream.range(0, i).filter(m -> i - m <= dist + 1)
                    .forEach(m -> dp[i][j] = Math.min(dp[i][j], dp[m][j - 1] + nums[m]));
            });
        });
        return IntStream.range(k, n + 1).map(i -> dp[i][k]).min().orElse(Integer.MAX_VALUE);
    }
}

该题解使用了两个堆（最大堆和最小堆）以及一个哈希表来维护和更新窗口中的元素，其中窗口大小由 dist 控制。窗口代表了可以作为子数组起始点的范围。解题思路的核心在于动态地维护k个子数组的最小总代价，通过在窗口中添加新元素，并从窗口移除旧元素。最大堆（pickedHeap）用于维护已选择的元素（负值表示，因为Python的heapq实现的是最小堆），而最小堆（unpickedHeap）用于维护未选择的元素。当一个新元素大于最大堆的堆顶时，它被加入到最小堆；反之，则替换最大堆的堆顶元素，并将旧的堆顶元素移到最小堆。这样可以保证当前窗口内的k个元素中，最小的元素总是位于最大堆的堆顶。哈希表（removesBook）用于记录已经从窗口中移除的元素的计数，以便在更新堆时正确处理这些元素。

O(n log k)

O(n)