Hard
题目描述
给你一个长度为 n 的下标从 0 开始的整数数组 nums，以及两个正整数 k 和 dist。
一个数组的 代价 是这个数组的 第一个 元素。比方说，[1,2,3] 的代价为 1，[3,4,1] 的代价为 3。
你需要将 nums 分割成 k 个 连续且互不相交 的子数组，满足第二个子数组与第 k 个子数组中第一个元素的下标距离 不超过 dist。换句话说，如果你将 nums 分割成子数组 nums[0..(i1 - 1)], nums[i1..(i2 - 1)], …, nums[ik-1..(n - 1)]，那么 ik-1 - i1 <= dist。
请你返回这些子数组 代价之和 的 最小值。
示例 1：
输入：nums = [1,3,2,6,4,2], k = 3, dist = 3
输出：5
解释：将数组分割成 3 个子数组的最佳方案是：[1,3], [2,6,4], 和 [2]。这个方案是合法的，因为 ik-1 - i1 是 5 - 2 = 3，等于 dist。总代价为 nums[0] + nums[2] + nums[5]，也就是 1 + 2 + 2 = 5。
可以证明没有别的方案可以得到更小的总代价 5。
示例 2：
输入：nums = [10,1,2,2,2,1], k = 4, dist = 3
输出：15
解释：将数组分割成 4 个子数组的最佳方案是：[10], [1], [2], 和 [2,2,1]。这个方案是合法的，因为 ik-1 - i1 是 3 - 1 = 2，小于 dist。总代价为 nums[0] + nums[1] + nums[2] + nums[3]，也就是 10 + 1 + 2 + 2 = 15。
分割方案 [10], [1], [2,2,2], 和 [1] 不合法，因为 ik-1 和 i1 的距离是 5 - 1 = 4，大于 dist。
可以证明没有别的方案可以得到更小的总代价 15。
示例 3：
输入：nums = [10,8,18,9], k = 3, dist = 1
输出：36
解释：将数组分割成 3 个子数组的最佳方案是：[10], [8], 和 [18,9]。这个方案是合法的，因为 ik-1 - i1 是 2 - 1 = 1，等于 dist。总代价为 nums[0] + nums[1] + nums[2]，也就是 10 + 8 + 18 = 36。
分割方案 [10], [8,18], 和 [9] 不合法，因为 ik-1 和 i1 的距离是 3 - 1 = 2，大于 dist。
可以证明没有别的方案可以得到更小的总代价 36。
提示：
3 <= n <= 10^51 <= nums[i] <= 10^93 <= k <= nk - 2 <= dist <= n - 2
解题思路
这道题的核心思想是枚举第二个子数组的起始位置，然后在满足距离限制的范围内找到最小的 k-2 个元素作为其余子数组的起始点。
解题思路：
枚举策略：第一个子数组必须从索引0开始，所以第一个代价是
nums[0]。我们枚举第二个子数组的起始位置i（范围是[1, n-k+1]），此时第二个子数组的代价是nums[i]。距离限制：根据题意，第
k个子数组的起始位置与第二个子数组起始位置的距离不能超过dist，即最后一个子数组的起始位置最多在i + dist。选择最小元素：在范围
[i+1, min(i+dist, n-1)]中选择k-2个最小的元素作为剩余子数组的起始点。双堆维护：使用两个堆来动态维护滑动窗口中的最小
k-2个元素：maxHeap：存储当前选中的k-2个最小元素（用最大堆，堆顶是这些元素中的最大值）minHeap：存储未选中的元素（用最小堆，堆顶是这些元素中的最小值）
滑动窗口更新：当窗口右边界扩展时添加新元素，左边界收缩时移除旧元素，并动态平衡两个堆，确保
maxHeap始终包含最小的k-2个元素。
这种方法能够在 O(n log n) 的时间复杂度内解决问题。
代码实现
class Solution {
public:
long long minimumCost(vector<int>& nums, int k, int dist) {
int n = nums.size();
long long result = LLONG_MAX;
// maxHeap stores the k-2 smallest elements (max at top)
priority_queue<pair<int, int>> maxHeap;
// minHeap stores the remaining elements (min at top)
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
multiset<pair<int, int>> maxSet, minSet;
for (int i = 1; i <= n - k + 1; i++) {
// Add new elements to the window
int right = min(i + dist, n - 1);
while (maxSet.size() + minSet.size() < right - i + 1) {
int idx = i + maxSet.size() + minSet.size();
if (maxSet.size() < k - 2) {
maxSet.insert({nums[idx], idx});
} else {
minSet.insert({nums[idx], idx});
}
}
// Remove elements that are out of window
int left = i + 1;
auto it = maxSet.lower_bound({0, left});
while (it != maxSet.begin() && prev(it)->second < left) {
it = maxSet.erase(prev(it));
}
it = minSet.lower_bound({0, left});
while (it != minSet.begin() && prev(it)->second < left) {
it = minSet.erase(prev(it));
}
// Balance the two sets
while (maxSet.size() < k - 2 && !minSet.empty()) {
auto minElem = *minSet.begin();
minSet.erase(minSet.begin());
maxSet.insert(minElem);
}
while (maxSet.size() > k - 2) {
auto maxElem = *maxSet.rbegin();
maxSet.erase(prev(maxSet.end()));
minSet.insert(maxElem);
}
while (!maxSet.empty() && !minSet.empty() &&
maxSet.rbegin()->first > minSet.begin()->first) {
auto maxElem = *maxSet.rbegin();
auto minElem = *minSet.begin();
maxSet.erase(prev(maxSet.end()));
minSet.erase(minSet.begin());
maxSet.insert(minElem);
minSet.insert(maxElem);
}
if (maxSet.size() == k - 2) {
long long cost = nums[0] + nums[i];
for (auto& p : maxSet) {
cost += p.first;
}
result = min(result, cost);
}
}
return result;
}
};
class Solution:
def minimumCost(self, nums: List[int], k: int, dist: int) -> int:
import heapq
from collections import defaultdict
n = len(nums)
result = float('inf')
# Use lists to simulate heaps with lazy deletion
max_heap = [] # negative values to simulate max heap
min_heap = []
max_heap_set = defaultdict(int)
min_heap_set = defaultdict(int)
def add_to_max_heap(val, idx):
heapq.heappush(max_heap, (-val, -idx))
max_heap_set[(val, idx)] += 1
def add_to_min_heap(val, idx):
heapq.heappush(min_heap, (val, idx))
min_heap_set[(val, idx)] += 1
def remove_from_max_heap(val, idx):
max_heap_set[(val, idx)] -= 1
if max_heap_set[(val, idx)] == 0:
del max_heap_set[(val, idx)]
def remove_from_min_heap(val, idx):
min_heap_set[(val, idx)] -= 1
if min_heap_set[(val, idx)] == 0:
del min_heap_set[(val, idx)]
def clean_max_heap():
while max_heap and (-max_heap[0][0], -max_heap[0][1]) not in max_heap_set:
heapq.heappop(max_heap)
def clean_min_heap():
while min_heap and (min_heap[0][0], min_heap[0][1]) not in min_heap_set:
heapq.heappop(min_heap)
def get_max_heap_size():
return len(max_heap_set)
def get_min_heap_size():
return len(min_heap_set)
for i in range(1, n - k + 2):
# Expand window to the right
right = min(i + dist, n - 1)
# Add elements in range [i+1, right]
for j in range(i + 1, right + 1):
if get_max_heap_size() < k - 2:
add_to_max_heap(nums[j], j)
else:
add_to_min_heap(nums[j], j)
# Remove elements that are out of window (< i+1)
to_remove = []
for (val, idx) in max_heap_set:
if idx < i + 1:
to_remove.append((val, idx))
for val, idx in to_remove:
remove_from_max_heap(val, idx)
to_remove = []
for (val, idx) in min_heap_set:
if idx < i + 1:
to_remove.append((val, idx))
for val, idx in to_remove:
remove_from_min_heap(val, idx)
# Balance heaps
while get_max_heap_size() < k - 2 and get_min_heap_size() > 0:
clean_min_heap()
if min_heap:
val, idx = heapq.heappop(min_heap)
remove_from_min_heap(val, idx)
add_to_max_heap(val, idx)
while get_max_heap_size() > k - 2:
clean_max_heap()
if max_heap:
neg_val, neg_idx = heapq.heappop(max_heap)
val, idx = -neg_val, -neg_idx
remove_from_max_heap(val, idx)
add_to_min_heap(val, idx)
# Swap if needed
while (get_max_heap_size() > 0 and get_min_heap_size() > 0):
clean_max_heap()
clean_min_heap()
if not max_heap or not min_heap:
break
max_val = -max_heap[0][0]
min_val = min_heap[0][0]
if max_val > min_val:
# Remove from max heap
neg_val, neg_idx = heapq.heappop(max_heap)
val1, idx1 = -neg_val, -neg_idx
remove_from_max_heap(val1, idx1)
# Remove from min heap
val2, idx2 = heapq.heappop(min_heap)
remove_from_min_heap(val2, idx2)
# Swap
add_to_max_heap(val2, idx2)
add_to_min_heap(val1, idx1)
else:
break
if get_max_heap_size() == k - 2:
cost = nums[0] + nums[i]
for val, idx in max_heap_set:
cost += val * max_heap_set[(val, idx)]
result = min(result, cost)
return result
public class Solution {
public long MinimumCost(int[] nums, int k, int dist) {
int n = nums.Length;
long result = long.MaxValue;
var maxSet = new SortedSet<(int val, int idx)>();
var minSet = new SortedSet<(int val, int idx)>();
for (int i = 1; i <= n - k + 1; i++) {
int right = Math.Min(i + dist, n - 1);
// Add new elements to window
for (int j = i + 1; j <= right; j++) {
if (maxSet.Count < k - 2) {
maxSet.Add((nums[j], j));
} else {
minSet.Add((nums[j], j));
}
}
// Remove elements out of window
var toRemoveFromMax = new List<(int, int)>();
var toRemoveFromMin = new List<(int, int)>();
foreach (var item in maxSet) {
if (item.idx < i + 1) {
toRemoveFromMax.Add(item);
}
}
foreach (var item in minSet) {
if (item.idx < i + 1) {
toRemoveFromMin.Add(item);
}
}
foreach (var item in toRemoveFromMax) {
maxSet.Remove(item);
}
foreach (var item in toRemoveFromMin) {
minSet.Remove(item);
}
// Balance sets
while (maxSet.Count < k - 2 && minSet.Count > 0) {
var minItem = minSet.Min;
minSet.Remove(minItem);
maxSet.Add(minItem);
}
while (maxSet.Count > k - 2) {
var maxItem = maxSet.Max;
maxSet.Remove(maxItem);
minSet.Add(maxItem);
}
while (maxSet.Count > 0 && minSet.Count > 0 &&
maxSet.Max.val > minSet.Min.val) {
var maxItem = maxSet.Max;
var minItem = minSet.Min;
maxSet.Remove(maxItem);
minSet.Remove(minItem);
maxSet.Add(minItem);
minSet.Add(maxItem);
}
if (maxSet.Count == k - 2) {
long cost = nums[0] + nums[i];
foreach (var item in maxSet) {
cost += item.val;
}
result = Math.Min(result, cost);
}
}
return result;
}
}
var minimumCost = function(nums, k, dist) {
const n = nums.length;
let result = Number.MAX_SAFE_INTEGER;
// Use arrays to simulate sorted sets
let maxSet = [];
let minSet = [];
const addToMaxSet = (val, idx) => {
maxSet.push([val, idx]);
maxSet.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
};
const addToMinSet = (val, idx) => {
minSet.push([val, idx]);
minSet.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
};
const removeFromMaxSet = (val, idx) => {
const index = maxSet.findIndex(item => item[0]
复杂度分析
| 项目 | 复杂度 |
|---|---|
| 时间复杂度 | O(n log n) |
| 空间复杂度 | O(n) |
解释：
- 时间复杂度：外层循环遍历 O(n) 个起始位置，每次操作涉及有序集合的插入、删除和查找操作，每个操作的时间复杂度为 O(log n)，总体时间复杂度为 O(n log n)
- 空间复杂度：需要维护两个有序集合存储元素，在最坏情况下需要存储 O(n) 个元素