Leetcode 3013. Divide an Array Into Subarrays With Minimum Cost II

本文主要是介绍Leetcode 3013. Divide an Array Into Subarrays With Minimum Cost II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode 3013. Divide an Array Into Subarrays With Minimum Cost II
- 1. 解题思路
- 2. 代码实现

题目链接：3013. Divide an Array Into Subarrays With Minimum Cost II

1. 解题思路

这一题的话思路上的话我一开始是想着偷懒直接用动态规划，结果果然还是遇到了超时的问题，因为事实上要遍历index和 $i_1$ 事实上也是一个 $O(N^2)$ 的算法复杂度，并不怎么现实。

但是后来我转念一想，这道题感觉我还是想复杂了，因为题目限制要求 $i_{k-1} - i_1 \leq d$ ，因此事实上就是要在长度为 $d$ 的窗口区间当中分为 $k$ 段，然后考察其中靠后的 $k - 1$ 段的开头元素的最小值。而这个事实上又完全等价于在这个长度为 $d$ 的窗口当中找出 $k - 1$ 个最小的元素即可。

因此，这道题也只需要遍历所有长度为 $d$ 的窗口，然后考察其中最小的 $k - 1$ 个元素的和的最小值然后加上第一个元素即可，而这就可以解答了，我们只需要用一个滑动窗口然后维护一下其中的各个元素以及前 $k - 1$ 个元素的和即可。

2. 代码实现

给出python代码实现如下：

class Solution:def minimumCost(self, nums: List[int], k: int, dist: int) -> int:n = len(nums)elems = sorted(nums[1:dist+2])s = sum(elems[:k-1])ans = sfor i in range(dist+2, n):idx = bisect.bisect_left(elems, nums[i])if idx < k-1:s = s + nums[i] - elems[k-2]elems.insert(idx, nums[i])idx = bisect.bisect_left(elems, nums[i-dist-1])if idx < k-1:s = s - elems[idx] + elems[k-1]elems.pop(idx)ans = min(ans, s)return ans + nums[0]