1493. Longest Subarray of 1's After Deleting One Element

📘 題目敘述

給定一個二元陣列 nums（只包含 0 和 1），你必須刪除恰好一個元素。

請回傳刪除後，陣列中「連續 1」的最長長度。

條件限制

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

🧠 解題思路

這題我用滑動視窗（Two Pointers）去找一段區間 [l, r]，讓它滿足：

視窗內最多只能有 1 個 0

因為題目規定「必須刪除 1 個元素」，所以：

• 如果視窗內有 1 個 0：刪掉那個 0，剩下全是 1
• 如果視窗內有 0 個 0（全部都是 1）：也得刪掉一個 1，所以答案會少 1

因此我在更新答案時，不是用 r - l + 1，而是用 r - l（等同於把視窗長度減 1，代表刪掉一個元素）。

所有變數

• l：滑動視窗左端點
• r：滑動視窗右端點（for 迴圈往右走）
• count：目前視窗內 0 的數量
• ans：目前找到的最大答案長度
• nums：輸入的二元陣列

🪜 主要流程步驟

1. 右指標 r 往右擴張

• 每次把 nums[r] 加進視窗
• 若 nums[r] == 0，就讓 count++

2. 視窗不合法就縮小

當 count > 1，代表視窗內 0 超過 1 個：

• 這樣就算只刪 1 個元素，也不可能讓剩下全是 1
• 所以要移動左指標 l 把視窗縮小

縮小時：

• 如果 nums[l] == 0，代表移出去一個 0，所以 count--
• 然後 l++
• 直到 count <= 1 視窗重新合法

3. 用 r - l 更新答案（重點）

視窗合法時 [l, r] 代表：

• 裡面最多只有一個 0
• 刪掉一個元素後，能得到的連續 1 長度就是「視窗長度 - 1」
• 視窗長度是 r - l + 1
• 所以答案更新用 r - l

ans = max(ans, r - l);

4. 為什麼全部都是 1 的情況也正確？

如果整段都沒有 0，例如 [1, 1, 1]：

• count 永遠是 0，不會進 while
• 但是題目規定一定要刪 1 個元素
• 用 r - l 會自然得到 n - 1，剛好就是必須刪掉一個 1 的結果

5. 複雜度

• 時間：O(n)（l 和 r 都只會往右走）
• 空間：O(1)

💻 程式碼實作

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int l = 0;
        int count = 0;
        int ans = 0;
        for (int r = 0; r < nums.size(); r++) {
            if (nums[r] == 0) {
                count++;
            }
            while (count > 1) {
                if (nums[l] == 0) {
                    count--;
                }
                l++;
            }
            ans = max(ans, r - l);
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/