🔗 🔴 995. Minimum Number of K Consecutive Bit Flips 1835

tags: `Weekly Contest 124` `差分陣列(Difference Array)` `前綴和(Prefix Sum)` `滑動窗口(Sliding Window)`

題意

給定一個二進位陣列 $nums$ 和一個整數 $k$ 。

在每次操作中，可以從 $nums$ 中選擇一個長度為 $k$ 的子陣列，同時將子陣列中的每個 $0$ 改為 $1$ ，每個 $1$ 改為 $0$ 。

返回使得陣列中沒有 $0$ 所需的最小操作次數。如果無法完成，請返回 $-1$ 。

子陣列(Subarray) 是指陣列的連續部分。

約束條件

$1 \leq n = nums.length \leq 10^5$
$1 \leq k \leq nums.length$

思路

這題跟 3191. Minimum Operations to Make Binary Array Elements Equal to One I 很類似，只是該題中的 $k = 3$ ，可以視為常數。在該題中，我們可以由前往後找到需要被翻轉的位置，並將大小為 $3$ 的區間直接翻轉。

但在此題中這樣做的話，時間複雜度為 $O(n \cdot k)$ ，當 $n = 10^5$ 時，會超時。因此我們需要找到更好的方法。

方法一：差分陣列(Difference Array)

首先將直接翻轉改為紀錄翻轉次數，因此翻轉次數為奇數的位置代表已經翻轉過，翻轉次數為偶數的位置代表未翻轉。若該位置為 $1$ 且翻轉次數為偶數、或該位置為 $0$ 且翻轉次數為奇數，則需要從當前位置開始翻轉 $k$ 個元素。

在紀錄翻轉次數時，需要使用到區間加法，而逐位加法的時間複雜度為 $O(k)$ ，因此需要找到更好的方法。為此可以使用差分陣列(Difference Array) ，這是一個與前綴和(Prefix Sum) 相對應的概念，可以在 $O(1)$ 的時間實現區間加法的功能，將區間 $[l, r]$ 上的所有數 $+1$ 可以轉換成對差分陣列的 $l$ 位置 $+1$ ， $r+1$ 位置 $-1$ ，最後再對差分陣列做前綴和即可還原出原始陣列。差分陣列的具體介紹本處省略，可以自行參考相關資料。

從左到右遍歷陣列 $nums$ ，當遇到需要翻轉的位置時，對差分陣列進行區間加法，並將翻轉次數加一。最後返回總共的翻轉次數即可，具體步驟如下：

令 $cur$ 表示當前位置的翻轉次數，對差分陣列求前綴和即可得到。
令 $diff$ $d i ff$ 表示翻轉次數的差分陣列，對於每個位置 $i$ $i$ ，若 $nums[i]$ $n u m s [i]$ 需要翻轉，則需要將 $[i, i+k)$ $[i, i + k)$ 區間的翻轉次數加一，即對 $diff[i]$ $d i ff [i]$ 加一，對 $diff[i+k]$ $d i ff [i + k]$ 減一。
- 由於 $diff[i]$ 只會在 $i$ 位置用到，因此可以省略對 $diff[i]$ 的加法操作，只需要對 $cur$ 加一即可。
- 在判斷是否需要翻轉時，可以由當前位置的翻轉次數 $cur$ $c u r$ 的奇偶性來判斷，若 $nums[i] = cur \And 1$ $n u m s [i] = c u r & 1$ ，則需要翻轉。
  - 由於 $nums[i]$ 已經被翻轉 $cur$ 次，因此當 $nums[i] = 0$ 且 $cur$ 是偶數，或 $nums[i] == 1$ 且 $cur$ 是奇數時，則需要翻轉。
- 若在需要翻轉時，若 $i+k > n$ ，則不足以翻轉以 $i$ 為起點的 $k$ 個元素，直接返回 $-1$ 。
最後返回 $ans$ 即可。

此外，由於我們在上述過程中只關注 $cur$ 和 $diff$ 陣列的奇偶性，因此可以將 $+1$ 操作改為 $\oplus 1$ ，為方便理解，在 Python 範例程式碼中不做這樣的優化，可見 C++ 範例程式碼。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ 。
空間複雜度： $\mathcal{O}(n)$ 。

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        n = len(nums)
        ans = 0 # 總共的翻轉次數
        cur = 0 # 當前位置的翻轉次數，對 diff 陣列求前綴和得出
        diff = [0] * (n + 1) # 翻轉次數的差分陣列
        for i, x in enumerate(nums):
            cur += diff[i] # 求前綴和
            if x == cur & 1: # 需要翻轉
                if i + k > n: # 無法翻轉
                    return -1
                ans += 1
                cur += 1
                # 將 [i, i + k) 區間的翻轉次數加一
                diff[i] += 1 # 由於後續用不到了，其實可以省略
                diff[i + k] -= 1
        return ans

class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = 0, cur = 0;
        vector<int> diff(n + 1, 0);
        for (int i = 0; i < n; i++) {
            cur ^= diff[i];
            if (nums[i] == cur) {
                if (i + k > n) return -1;
                ans++;
                cur ^= 1;
                diff[i + k] ^= 1;
            }
        }
        return ans;
    }
};

方法二：滑動窗口(Sliding Window)

根據方法一，當遍歷到位置 $i$ 時，若 $i-k$ 位置上發生了翻轉操作，則當前位置的翻轉次數 $cur$ 需要減一。從這個角度出發，可以不使用 $diff$ 陣列，而是跟據 $i-k$ 位置的狀態來直接修改 $cur$ ，也就是在加入右側的元素時，考慮左側的元素的狀態，這種方式和滑動窗口(Sliding Window) 的思想相符。

為了得知 $i-k$ 位置上是否發生了翻轉操作，需要使用一些標記方式。例如使用一個額外陣列來表示該位置的翻轉次數，但這樣會增加空間複雜度。由於 $0 \leq nums[i] \leq 1$ ，我們可以將 $nums[i]$ 的範圍之外的數來表示該位置「是否翻轉過」。

若翻轉從位置 $i$ 開始的子陣列，可以將 $nums[i]$ 加 $2$ ，這樣當遍歷到位置 $i'$ 時，若有 $nums[i'-k] > 1$ ，則說明在位置 $i'-k$ 上發生了翻轉操作。
若需要還原原始陣列，只需要將 $nums[i]$ 減 $2$ 即可。

具體步驟如下：

令 $ans$ 表示總共的翻轉次數， $cur$ 表示窗口內的翻轉次數，皆初始化為 $0$ 。
接著遍歷 $nums$ $n u m s$ 陣列，對於每個位置 $i$ $i$ ：
- 當 $i \geq k$ 時，需要檢查窗口左側的元素是否發生了翻轉操作，若是，則需要將 $cur$ 減一。
- 若 $nums[i]$ $n u m s [i]$ 需要翻轉，即當 $nums[i] = cur \And 1$ $n u m s [i] = c u r & 1$ 時，則需要標記從位置 $i$ $i$ 開始的 $k$ $k$ 個元素已經翻轉過，並將 $cur$ $c u r$ 加一。
  - 透過將 $nums[i]$ 加二來標記這個位置，代表從這個位置開始的 $k$ 個元素被翻轉過。
  - 若此時 $i+k-1 > n-1$ ，則無法翻轉從位置 $i$ 開始的 $k$ 個元素，直接返回 $-1$ 。
最後返回 $ans$ 即可。

同樣的，由於我們在上述過程中只關注 $cur$ 的奇偶性，因此可以將 $+1$ 操作改為 $\oplus 1$ ，為方便理解，在 Python 範例程式碼中不做這樣的優化，可見 C++ 範例程式碼。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ 。
空間複雜度： $\mathcal{O}(1)$ 。

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        n = len(nums)
        ans = 0 # 總共的翻轉次數
        cur = 0 # 窗口內的翻轉次數
        for i in range(n):
            if i >= k: # 窗口有超過 k 個元素時才需要出窗口
                if nums[i - k] > 1: # i - k 位置被翻轉過，當前位置的翻轉次數時需要減一
                    cur -= 1
                    nums[i - k] -= 2 # 取消標記
            if nums[i] == (cur & 1): # 需要翻轉
                if i + k - 1 > n - 1: # 無法翻轉
                    return -1
                nums[i] += 2 # 標記這個位置，代表從這個位置開始的 k 個元素被翻轉過
                cur += 1
                ans += 1
        return ans

class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = 0, cur = 0;
        for (int i = 0; i < n; i++) {
            if (i >= k && nums[i - k] > 1) {
                cur ^= 1;
                nums[i - k] -= 2;
            }
            if (nums[i] == cur) {
                if (i + k > n) return -1;
                nums[i] += 2;
                cur ^= 1;
                ans++;
            }
        }
        return ans;
    }
};