LeetCode——最大連續1的個數 III（滑動視窗）

這是我參與8月更文挑戰的第12天，活動詳情檢視： 8月更文挑戰

題目描述

解題思路

本題的核心思路是滑動視窗，而滑動視窗的實作需要借助雙指針，這是解決本題的核心思路。

1. 定義滑動視窗的左右邊界。

let l = 0;
let r = 0;
複制代碼      

1. 定義滑動視窗中連續1的個數（包含K個零）

let max = 0;
複制代碼      

1. 定義滑動視窗中零的個數。

let zeros = 0;
複制代碼      

1. 核心循環體

• 進入循環的條件是右邊界越界

while (r < nums.length)
複制代碼      

• 判斷滑動視窗中零的個數和K的關系

隻有兩種關系，要麼滑動視窗中零的個數小于等于K,要麼大于K，如果小于K，說明視窗右邊界還未滿足條件，還需要繼續擴充右邊界，此時讓r++,但是在右邊界擴充的時候，我們要看目前右指針指向的元素是0還是1，如果是1則直接向右擴充即可，但是如果是1，則需要更新0的個數之後，繼續擴充，如果零的個數大于K，則需要移動左邊界，在移動左邊界的時候，依然要考慮上述因素。

if (zeros <= k) {
        if (nums[r] === 1) {
            r++;
        } else {
            r++;
            zeros++;
        }
    }
    if (zeros > k) {
        if (nums[l] === 0) {
            zeros--;
            l++;
        } else {
            l++;
        }
    }
複制代碼      

• 更新最大值（因為r總是先移動後判斷，是以用右邊界-左邊界就可以和最大值進行比較更新）

if (r - l > max) {
    max = r - l;
}
複制代碼      

AC代碼

// 核心思路: 滑動視窗 + 更新最大值
var longestOnes = function (nums, k) {
    // 定義滑動視窗的左右邊界
    let l = 0;
    let r = 0;
    // 定義滑動視窗中連續1（包含K個零）的最大值
    let max = 0;
    // 定義滑動視窗中0的個數
    let zeros = 0;
    // 進入循環的條件是：滑動視窗的右邊界沒有越界
    while (r < nums.length) {
        if (zeros <= k) {
            if (nums[r] === 1) {
                r++;
            } else {
                r++;
                zeros++;
            }
        }
        if (zeros > k) {
            if (nums[l] === 0) {
                zeros--;
                l++;
            } else {
                l++;
            }
        }
        if (r - l > max) {
            max = r - l;
        }
    }
    return max;
};
複制代碼      

執行結果

題目反思

• 學會使用滑動視窗的方式求解子區間、子數組問題。
• 學會使用更新的方式擷取最大值。