算法学习之滑动窗口

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

给你一个整数数组 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 。
示例 2：
输入：nums = [1,0,0,0,0,0,1,1], k = 3
输出：5
解释：通过 5 次操作，最左边的 1 可以移到右边直到 nums 变为 [0,0,0,0,0,1,1,1] 。
示例 3：
输入：nums = [1,1,0,1], k = 2
输出：0
解释：nums 已经有连续 2 个 1 了。
提示：
1 <= nums.length <= 105
nums[i] 要么是 0 ，要么是 1 。
1 <= k <= sum(nums)

思路：
构建新的数组 int zero[], zero的元素值表示相邻两个1之间的0的个数。
然后，在zero数组上进行滑动窗口计算。
注意：在zero上滑动窗口的大小为k - 1。对于窗口中每个位置的cost，就像一座山峰一样，两端是1，往中间逐个递增。我们这里第一个窗口的cost是[1, 2, 2, 1]。

class Solution {
    public int minMoves(int[] nums, int k) {
        List<Integer> zeros = new ArrayList<>();
        int count0 = 0, count1 = 0;
        for (int num : nums) {
            if (num != 1) count0++;
            else {
                if (count1 != 0) zeros.add(count0);
                count1++;
                count0 = 0;
            }
        }
        int[] preSum = new int[zeros.size() + 1];
        for (int i = 0; i < zeros.size(); i++) {
            preSum[i + 1] = preSum[i] + zeros.get(i);
        }
        int cost = 0;
        int left = 0, right = k - 2;
        for (int i = left; i <= right; i++) {
            cost += zeros.get(i) * (Math.min(i + 1, right - i + 1));
        }
        int minCost = cost;
        for (int i = 1, j = i + k - 2; j < zeros.size(); i++, j++) {
            int mid = (i + j) / 2;
            cost -= preSum[mid] - preSum[i - 1];
            cost += preSum[j + 1] - preSum[mid + k % 2];
            minCost = Math.min(minCost, cost);
        }
        return minCost;
    }
}