★ FEATURED ARTICLE 3505. 使 K 个子数组内元素相等的最少操作数网页链接力扣LeetCode力扣LeetCode 每日一题完成每日打卡即可获得力扣积分。获得相应数量的积分能在【力扣商店】换取相应奖品助力每日有题做丰盈积分日益多题目描述给你一个整数数组nums和两个整数x和k。你可以执行以下操作任意次包括零次将nums中的任意一个元素加1或减1。返回为了使nums中至少包含k个长度恰好为x的不重叠子数组每个子数组中的所有元素都相等所需要的最少操作数。子数组是数组中连续、非空的一段元素。输入描述一个整数数组nums两个整数x和k。输出描述返回使nums中至少包含k个长度为x且内部元素全部相等的不重叠子数组所需的最少操作数。示例示例 1输入nums [5,-2,1,3,7,3,6,4,-1], x 3, k 2输出8解释进行 3 次操作将nums[1]加 3进行 2 次操作将nums[3]减 2。得到的数组为[5, 1, 1, 1, 7, 3, 6, 4, -1]。进行 1 次操作将nums[5]加 1进行 2 次操作将nums[6]减 2。得到的数组为[5, 1, 1, 1, 7, 4, 4, 4, -1]。现在子数组[1, 1, 1]下标 1 到 3和[4, 4, 4]下标 5 到 7中的所有元素都相等。总共进行了 8 次操作因此输出为 8。示例 2输入nums [9,-2,-2,-2,1,5], x 2, k 2输出3解释进行 3 次操作将nums[4]减 3。得到的数组为[9, -2, -2, -2, -2, 5]。现在子数组[-2, -2]下标 1 到 2和[-2, -2]下标 3 到 4中的所有元素都相等。总共进行了 3 次操作因此输出为 3。数据范围2 ≤ nums.length ≤ 10 5 2 \le \text{nums.length} \le 10^52≤nums.length≤105− 10 6 ≤ nums [ i ] ≤ 10 6 -10^6 \le \text{nums}[i] \le 10^6−106≤nums[i]≤1062 ≤ x ≤ nums.length 2 \le x \le \text{nums.length}2≤x≤nums.length1 ≤ k ≤ 15 1 \le k \le 151≤k≤152 ≤ k × x ≤ nums.length 2 \le k \times x \le \text{nums.length}2≤k×x≤nums.length解题思路本题是滑动窗口中位数 线性动态规划问题。需要先在每个长度为x的连续子数组上求出“把该子数组内所有元素变成相等”的最小操作数然后从所有长度为x的子数组中选出至少k个互不重叠的使总操作数最小。由于每个子数组的代价非负选择多于k个不会让答案更优因此“至少k个”等价于“恰好k个”。1. 单个长度为 x 的子数组的代价对于一个长度为x的数组每次操作可以让某个元素加1或减1。要把所有元素变成相等目标值取该数组的中位数时总操作数最小。设中位数为v则代价为∑ i ∣ a i − v ∣ \sum_i |a_i-v|i∑∣ai−v∣用两个堆维护窗口内元素大根堆L保存较小的一半小根堆R保存较大的一半保持L.size() R.size()或L.size() R.size() 1此时L.top()就是中位数。维护两个堆的元素和sumL、sumR。当前窗口中位数v L.top()时窗口代价为v × ∣ L ∣ − s u m L s u m R − v × ∣ R ∣ v \times |L| - sumL sumR - v \times |R|v×∣L∣−sumLsumR−v×∣R∣为了支持滑动窗口删除左端元素代码使用懒删除堆删除元素时不直接从堆中删除而是记录待删除次数取堆顶时再清理。这样可以在O ( log n ) O(\log n)O(logn)时间内完成每次插入、删除和查询中位数。对数组nums做一次长度为x的滑动窗口得到数组d其中d [ s ] 将 n u m s [ s . . s x − 1 ] 变为全部相等的最小操作数 d[s] \text{将 } nums[s..sx-1] \text{ 变为全部相等的最小操作数}d[s]将nums[s..sx−1]变为全部相等的最小操作数d的长度为n - x 1。2. 动态规划选择不重叠子数组设f[i][j]表示只考虑前j个元素下标0..j-1选出i个长度为x的不重叠子数组时的最小总代价。初始时f [ 0 ] [ j ] 0 f[0][j] 0f[0][j]0因为选0个子数组代价为0。对于第i个子数组处理到前j个元素时有两种选择不选以j-1结尾的窗口继承前j-1个元素的结果f [ i ] [ j ] f [ i ] [ j − 1 ] f[i][j] f[i][j-1]f[i][j]f[i][j−1]选择一个窗口该窗口长度为x覆盖下标[j-x, j-1]其代价为d[j-x]。选择它之前前j-x个元素中已经选好了i-1个子数组f [ i ] [ j ] f [ i − 1 ] [ j − x ] d [ j − x ] f[i][j] f[i-1][j-x] d[j-x]f[i][j]f[i−1][j−x]d[j−x]因此转移方程为f [ i ] [ j ] min ( f [ i ] [ j − 1 ] , f [ i − 1 ] [ j − x ] d [ j − x ] ) f[i][j] \min\bigl(f[i][j-1],\ f[i-1][j-x] d[j-x]\bigr)f[i][j]min(f[i][j−1],f[i−1][j−x]d[j−x])其中j至少为i*x否则不可能放下i个长度为x的子数组。代码中把f[i][i*x-1]设为无穷大表示非法状态然后从j i*x开始转移。由于后面还要选k-i个子数组需要预留至少(k-i)*x个位置因此第i层只计算到j ≤ n − ( k − i ) x j \le n - (k-i)xj≤n−(k−i)x最后一层ik时上界就是n。最终答案为f [ k ] [ n ] f[k][n]f[k][n]3. 复杂度分析滑动窗口中位数每个元素最多进出堆一次每次堆操作O ( log n ) O(\log n)O(logn)总时间O ( n log n ) O(n\log n)O(nlogn)动态规划状态数O ( k n ) O(kn)O(kn)每个状态O ( 1 ) O(1)O(1)转移时间O ( k n ) O(kn)O(kn)总时间复杂度O ( n log n k n ) O(n\log n kn)O(nlognkn)空间复杂度中位数部分O ( n ) O(n)O(n)DP 部分O ( k n ) O(kn)O(kn)总体O ( n k n ) O(n kn)O(nkn)。总结先用两个懒删除堆维护长度为x的滑动窗口的中位数求出每个窗口内部变为全部相等的最小代价得到代价数组d。再用动态规划从前向后选择恰好k个不重叠窗口转移时考虑“不选当前结尾窗口”和“选以当前位置结尾的窗口”两种情况。最终f[k][n]即为最小总操作数。代码内容templatetypenameT,typenameComparelessTclassLazyHeap{priority_queueT,vectorT,Comparep;unordered_mapT,intrc;// 待删除次数size_t z0;// 实际大小longlongsm0;// 元素总和voidar(){// 执行懒删除while(!p.empty()rc[p.top()]0){rc[p.top()]--;p.pop();}}public:size_tsize(){returnz;}longlongsum(){returnsm;}voidremove(T x){rc[x];z--;sm-x;}Ttop(){ar();returnp.top();}Tpop(){ar();T xp.top();p.pop();z--;sm-x;returnx;}voidpush(T x){if(rc[x]0){rc[x]--;}else{p.push(x);}z;smx;}Tpush_pop(T x){ar();p.push(x);smx;xp.top();p.pop();sm-x;returnx;}};classSolution{// 返回所有长为 w 的子数组到其中位数的距离和vectorlonglongms(vectorinta,intw){intna.size();vectorlonglongr(n-w1);LazyHeapintL;// 最大堆LazyHeapint,greaterR;// 最小堆for(inti0;in;i){intina[i];if(L.size()R.size()){L.push(R.push_pop(in));}else{R.push(L.push_pop(in));}intli1-w;if(l0){continue;}longlongvL.top();longlongs1v*L.size()-L.sum();longlongs2R.sum()-v*R.size();r[l]s1s2;intouta[l];if(outL.top()){L.remove(out);if(L.size()R.size()){L.push(R.pop());}}else{R.remove(out);if(L.size()R.size()1){R.push(L.pop());}}}returnr;}public:longlongminOperations(vectorinta,intx,intk){intna.size();vectorlonglongdms(a,x);vectorf(k1,vectorlonglong(n1));for(inti1;ik;i){f[i][i*x-1]LLONG_MAX;for(intji*x;jn-(k-i)*x;j){f[i][j]min(f[i][j-1],f[i-1][j-x]d[j-x]);}}returnf[k][n];}};
阅读完成 · 觉得有帮助？
