接續昨天主題 sliding window ，但我昨日想說要寫 leetcode 第 30 題，但它比我想像中棘手，明天再繼續寫那題，希望能有比較清晰的思路知道如何解題!
本日就只練習了第 1004 題

1004. Max Consecutive Ones III medium

題目敘述:
給一個陣列跟一個整數 k，k 是代表能夠把 0 變 1 的次數。返回最多 有多少個連續 1。

例如:
給定陣列 nums = [0,0,1,0,1,1,0] 和 k = 2，這表示最多可以將 2 個 0 變為 1

結果: 返回5，因為當第 3 與 6 的值 (0-index)翻成 1 就能得到最長連續 1

此題解題思路:思考何時 rptr 移動 與 lptr 何時移動?

能夠擴張視窗的情況有 第一是 rptr 指向的值是1，無所擔憂的直接擴張。第二是第 rptr 的值是 0 但 k > 0 所以也能擴張視窗。 其餘情況，就得移動 lptr 將視窗縮小。

這題的迴圈不變性在於要記錄視窗內的 1 出現次數

因此程式碼這樣寫:

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int lptr = 0, rptr = 0, ctr = 0, maxOne = 0;
        while (rptr < nums.size()) {
            // rptr moves
            if (nums[rptr]) {
                maxOne = max(++ctr, maxOne);
                rptr++;
            }
            else if (k > 0) {
                k--;
                rptr++;
                maxOne = max(++ctr, maxOne);
            }
            else { // If there is no k available, the window must be reduced and lptr moved to the right
                if (nums[lptr++] == 0) {
                    k++;
                }
                ctr--;
            }
        }
        return maxOne;
    }
};

時間複雜度: O(n)

今天透過練習 LeetCode 第 1004 題，進一步鞏固了 sliding window 的概念。明天我會回頭挑戰 LeetCode 第 30 題!