绝对值不等式.pdf

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)

思路：
首先转换成货舱选址问题，然后考虑总移动距离的计算

  1. 目标是使得k个1连续，故只考虑1即可，将每个1在原数组的位置抠出，组成一个新数组
  2. 使用长为k的滑动窗口进行考虑，当前窗口内的元素对应一个个货舱，目标是将他们移动到一起并使得总代价最小
  3. 类似货舱选址，选择中位数，接下来的问题就是移动距离的总和如何计算？

  4. 考虑使用前缀和，分开计算中位数左边和右边的元素与目的地之间的距离

    1. class Solution {
    2. public int minMoves(int[] nums, int k) {
    3.   List<Integer> list = new ArrayList<>();
    4.   for (int i = 0; i < nums.length; i++)
    5.       if (nums[i] == 1)
    6.           list.add(i);
    8.   int n = list.size();
    9.   int[] pre = new int[n + 1];
    10.   for (int i = 1; i <= n; i++) {
    11.       pre[i] = pre[i - 1] + list.get(i - 1);
    12.   }
    14.   int min = Integer.MAX_VALUE;
    15.   for (int i = 1, j = 1; i <= n; i++) {
    16.       if (i - j + 1 >= k) {
    17.           int mid = i + j >> 1;
    18.           int v = list.get(mid - 1);
    19.           min = Math.min(min, v * (mid - j + 1) - pre[mid] + pre[j - 1] - get(mid - j) 
    20.                          - v * (i - mid + 1) + pre[i] - pre[mid -  1] - get(i - mid));
    21.           j++;
    22.       }
    23.   }
    24.   return min;
    25. }
    27. int get(int size) {
    28.   return (size + 1) * size / 2;
    29. }
    30. }

    1703的简化版：2134. 最少交换次数来组合所有的 1 II