LeetCode 2134. 最少交換次數來組合所有的 1 II（環形陣列＋定長滑動視窗圖解）

2134. 最少交換次數來組合所有的 1 II

題目描述

交換定義為選中一個陣列中的兩個互不相同的位置並交換二者的值。

環形陣列是一個陣列，可以認為第一個元素和最後一個元素相鄰。

給你一個二進位環形陣列 nums，回傳在任意位置將陣列中的所有 1 聚集在一起需要的最少交換次數。

範例 1

輸入：nums = [0,1,0,1,1,0,0]
輸出：1
解釋：這裡列出一些能夠將所有 1 聚集在一起的方案：
[0,0,1,1,1,0,0] 交換 1 次。
[0,1,1,1,0,0,0] 交換 1 次。
[1,1,0,0,0,0,1] 交換 2 次（利用陣列的環形特性）。
無法在交換 0 次的情況下將陣列中的所有 1 聚集在一起。
因此，需要的最少交換次數為 1。

範例 2

輸入：nums = [0,1,1,1,0,0,1,1,0]
輸出：2
解釋：這裡列出一些能夠將所有 1 聚集在一起的方案：
[1,1,1,0,0,0,0,1,1] 交換 2 次（利用陣列的環形特性）。
[1,1,1,1,1,0,0,0,0] 交換 2 次。
無法在交換 0 次或 1 次的情況下將陣列中的所有 1 聚集在一起。
因此，需要的最少交換次數為 2。

範例 3

輸入：nums = [1,1,0,0,1]
輸出：0
解釋：得益於陣列的環形特性，所有的 1 已經聚集在一起。
因此，需要的最少交換次數為 0。

限制

• 1 <= nums.length <= 10^5
• nums[i] 為 0 或者 1

本文題解思路與程式碼整理自 LeetCode 題解作者「灵茶山艾府」，題解連結。圖解與步驟說明為自行補充。

前置知識：定長滑動視窗

定長視窗每次右移一格，少一個最左邊的元素、多一個新元素，視窗內的和可以用「加新的、減舊的」在 O(1) 內更新。前面幾篇已經用過，例如 2841、1423。這題多了一個「環形」，要處理視窗跨過尾巴的情況。

思路

這題的操作是「交換」，看起來很難算。但可以用一個簡單的等價問題取代：最後所有的 1 會擠在一段連續的位置裡，那一段的長度一定是 1 的總個數。

第一步：目標是一個長度為 k 的全 1 視窗

設 nums 裡有 k 個 1。把所有 1 聚在一起，最後就是某一段長度為 k 的連續位置全是 1（環形陣列裡，這一段可以從尾巴繞回開頭）。

所以問題變成：選一段長度為 k 的視窗，把它變成全 1，最少要交換幾次？

第二步：交換次數 = 視窗內 0 的個數

• 視窗內本來就是 1 的位置，不用動。
• 視窗內是 0 的位置，把它和視窗外的某個 1 交換，就能把一個 1 換進視窗。

視窗內 0 的個數，一定等於視窗外 1 的個數，因為全部 1 剛好 k 個、視窗長度也是 k：

視窗內的 1 + 視窗外的 1 = k = 視窗內的 1 + 視窗內的 0
⇒ 視窗外的 1 = 視窗內的 0

所以視窗內的 0 和視窗外的 1 可以一一配對，每交換一對，就多一個 1 進視窗，共需要「視窗內 0 的個數」次，而且沒有更省的做法。

用範例 1 看看。k = 3，每個視窗（含繞回的）內有幾個 0，就要交換幾次：

上一個視窗 下一個視窗 重置

nums = [0,1,0,1,1,0,0]（k = 3 個 1，所以視窗長度 = 3；陣列是環形，視窗可以從尾巴繞回開頭）

視窗（要變成全 1） 1 0

視窗內 0 的個數 = 需要交換的次數0

所有視窗中的最小值0

七個視窗內 0 的個數依序是 2、1、1、1、2、3、2，最小值是 1，就是範例 1 的答案。

於是問題變成：

環形陣列中，長度為 k 的視窗裡 0 的個數的最小值。

這是標準的定長滑動視窗。

第三步：處理環形陣列

視窗要從尾巴繞回開頭怎麼辦？把陣列想成攤平的序列，接在後面再複製一段，下標超過 n − 1 就取模 n 映射回原本的位置：

• 第一個視窗是 [0, k − 1]，最後一個視窗是 [n − 1, n + k − 2]。
• [n − 1, n + k − 2] 的下一個視窗是 [n, n + k − 1]，在環形陣列裡這和 [0, k − 1] 完全一樣，所以不需要再繼續枚舉。
• 因此 i 只需要從 0 走到 n + k − 2，進入視窗的元素用 nums[i % n]。
• 離開視窗的元素 nums[i − k + 1]，因為 i < n + k − 1，所以 i − k + 1 < n，不用取模。

第四步：統計 1 比統計 0 方便

視窗內 0 的個數 = k − 視窗內 1 的個數。與其數 0，不如數 1（直接把元素加起來，因為元素就是 0 或 1），先求視窗內 1 的個數的最大值 max1，最後答案就是 k − max1。

特別情況：陣列裡完全沒有 1（k = 0），不需要交換，直接回傳 0。

圖解（可互動）

用範例 1：nums = [0,1,0,1,1,0,0]，k = 3，n = 7。陣列被攤平成長度 n + k − 1 = 9 的序列，虛線格是接在後面複製的那兩格（下標 7、8，對應原本的 0、1）。重點看：

• 前 k − 1 = 2 個元素只累加、不更新答案（窗口還沒滿）。
• 窗口 [5, 7]、[6, 8] 是跨過尾巴的窗口，用的是 nums[i % n]。
• max1 最後是 2，答案 = 3 − 2 = 1。

上一步 下一步 重置

nums = [0,1,0,1,1,0,0]，n = 7，k = 3：把陣列「攤平」成長度 n + k − 1 = 9 的序列（虛線格是接在後面的複製，下標要 % n）

視窗 環形接回來的複製 入 = 新進入 出 = 更新後離開

視窗內 1 的個數 cnt10

目前最大值 max10

把過程寫成表格（n = 7，k = 3）：

窗口	內容	窗口內 1 的個數	max1	窗口內 0 的個數
[0,2]	0,1,0	1	1	2
[1,3]	1,0,1	2	2	1
[2,4]	0,1,1	2	2	1
[3,5]	1,1,0	2	2	1
[4,6]	1,0,0	1	2	2
[5,7]	0,0,0（nums[7%7]=nums[0]）	0	2	3
[6,8]	0,0,1（nums[0]、nums[1]）	1	2	2

答案 = k − max1 = 3 − 2 = 1。

解法（灵茶山艾府）

class Solution {
    public int minSwaps(int[] nums) {
        // 統計 1 的個數
        int k = 0;
        for (int x : nums) {
            k += x;
        }
        if (k == 0) { // 沒有 1，無需交換
            return 0;
        }

        int n = nums.length;
        int max1 = 0;
        int cnt1 = 0;
        for (int i = 0; i < n + k - 1; i++) {
            // 1. 進入視窗
            cnt1 += nums[i % n];
            if (i < k - 1) { // 視窗大小不足 k
                continue;
            }
            // 2. 更新答案
            max1 = Math.max(max1, cnt1);
            // 3. 離開視窗，為下一個迴圈做準備
            cnt1 -= nums[i - k + 1]; // 由於我們保證 i < n+k-1，所以 i-k+1 < n，無需取模
        }
        return k - max1;
    }
}

幾個細節：

• i 的範圍是 0 ~ n + k − 2，這樣剛好窗口起點 0 ~ n − 1 各一次，不會重複。
• 進入視窗要取 i % n，離開視窗不用，因為 i − k + 1 < n。
• 整個陣列都是 1（k = n）時，max1 = k，答案是 0，不需要特別處理。

複雜度分析

• 時間複雜度：O(n)，其中 n 是 nums 的長度。統計 1 的個數 O(n)，滑動視窗最多走 n + k − 1 ≤ 2n − 1 步。
• 空間複雜度：O(1)。