解题思路
题目要求通过最少次数的加 1 或减 1 操作(数字只能在 0 到 9 之间变化),使得序列中存在一个长度为 k 的连续子序列,其内部所有数字完全相同。
由于最终相同的数字只可能是 0 到 9 中的某一个,我们可以采用以下策略:
- 枚举目标数字:依次假设最终相同的数字为 d(d=0,1,…,9)。
- 计算窗口代价:对于每一个目标数字 d,我们需要找到一个长度为 k 的子数组 a[i…i+k−1],将它里面的所有元素都变成 d 所需的操作总次数 ∑j=ii+k−1∣aj−d∣ 最小。
- 滑动窗口优化:对固定的 d,如果对每一个长度为 k 的子数组都重新求和,复杂度会很高。我们可以先计算第一个窗口 [0,k−1] 的代价,然后窗口向右滑动时,去掉左边移出窗口的元素 a[i−k] 的贡献,加上右边新进入窗口的元素 a[i] 的贡献,即
cost = cost - |a[i-k] - d| + |a[i] - d|,从而实现 O(1) 更新。