LC-1703.得到连续K个1的最少相邻交换次数

题目描述

leetcode 困难题

给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1 。每一次移动，你可以选择 相邻 两个数字并将它们交换。

请你返回使 nums 中包含 k 个 连续 1 的 最少 交换次数。

示例1：

输入：nums = [1,0,0,1,0,1], k = 2
输出：1
解释：在第一次操作时，nums 可以变成 [1,0,0,0,1,1] 得到连续两个 1 。

提示1：

1 <= nums.length <= 105
nums[i] 要么是 0 ，要么是 1 。
1 <= k <= sum(nums)

TODO-分析

AcWing104.货仓选址

AcWing104.货仓选址

绝对值不等式-wiki

class Solution {
    public int minMoves(int[] nums, int k) {
        int n = nums.length;
        List<Integer> p = new ArrayList<>();
        for(int i = 0; i < n; i++){
            if(nums[i] == 1){
                p.add(i - p.size()); // p = q_i - i
            }
        }
        int[] s = new int[p.size() + 1];
        for(int i = 1; i <= p.size(); i++){
            s[i] = s[i - 1] + p.get(i - 1);
        }
        int ans = Integer.MAX_VALUE;
        for(int i = 0; i <= p.size() - k; i++){
            ans = Math.min(ans, s[i] + s[i + k] - (2 * s[i + k / 2]) - (p.get(i + k / 2) * (k % 2)));
        }
        return ans;
    }
}