Longest Subarray of 1's After Deleting One Element
題目描述
給定二進位陣列 nums，刪除恰好一個元素後，回傳最長的全 1 子陣列長度。
輸入：nums = [1,1,0,1,1,1,0,1,1]
輸出：5（刪除 nums[2]，得到 [1,1,1,1,1]）
輸入：nums = [0,1,1,1,0,1,1,0,1]
輸出：4
輸入：nums = [1,1,1]
輸出：2（必須刪除一個元素）
解題思路
等同上題
滑動窗口允許最多 1 個 0（k=1）
擴張右邊
right 往右移，追蹤 0 的數量
收縮左邊
0 的數量超過 1 時，left 收縮
結果減一
窗口長度 - 1 就是刪除一個元素後的長度
程式碼
C#
public class Solution {
public int LongestSubarray(int[] nums) {
int left = 0, zeroCount = 0, maxLen = 0;
for (int right = 0; right < nums.Length; right++) {
if (nums[right] == 0) zeroCount++;
while (zeroCount > 1) {
if (nums[left] == 0) zeroCount--;
left++;
}
// 窗口長度 - 1（因為必須刪除一個元素）
maxLen = Math.Max(maxLen, right - left);
}
return maxLen;
}
}TypeScript
function longestSubarray(nums: number[]): number {
let left = 0, zeroCount = 0, maxLen = 0;
for (let right = 0; right < nums.length; right++) {
if (nums[right] === 0) zeroCount++;
while (zeroCount > 1) {
if (nums[left] === 0) zeroCount--;
left++;
}
maxLen = Math.max(maxLen, right - left); // 不是 right-left+1
}
return maxLen;
}Python
def longestSubarray(nums: list[int]) -> int:
left = zero_count = max_len = 0
for right in range(len(nums)):
if nums[right] == 0:
zero_count += 1
while zero_count > 1:
if nums[left] == 0:
zero_count -= 1
left += 1
# right - left 而非 right - left + 1
max_len = max(max_len, right - left)
return max_len複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |
- Time：left 和 right 各最多走 n 步，合計 O(2n) = O(n)，每步只做常數操作
- Space：只用了 left、zeroCount、maxLen 三個變數，不隨輸入增長
圖解
圖表展示了核心策略：滑動窗口最多允許包含 1 個 0，找到最長的窗口 [1,1,0,1,1,1] 長度為 6。
因為必須刪除一個元素（那個 0），實際全 1 子陣列長度為 6-1=5。
邊界情況
- 全部是 1：沒有 0 可以刪除，但題目要求必須刪一個元素，所以答案是 n-1。窗口覆蓋整個陣列，
right - left = n - 1正好正確 - 全部是 0：窗口最多包含 1 個 0，長度為 1，
right - left = 0，答案為 0（刪掉那個 0 後沒有 1） - 只有一個元素：
[1]→ 刪掉後為空，答案 0；[0]→ 刪掉後也為空，答案 0
進階觀點
💡面試追問
Q: 為什麼是 right - left 而不是 right - left + 1？
A: 正常滑動窗口長度是 right - left + 1，但這題必須刪除一個元素，所以長度要減 1，變成 right - left + 1 - 1 = right - left。
Q: 全是 1 的陣列怎麼辦？
A: 仍然必須刪除一個元素，所以答案是 n-1。公式 right - left 在全 1 時，最大窗口覆蓋整個陣列（left=0, right=n-1），right - left = n - 1，正好正確。
Q: 跟 Max Consecutive Ones III 的本質差異？
A: 翻轉是「把 0 變 1，元素數量不變」，刪除是「移除一個元素，總長度少 1」。兩者的滑動窗口邏輯完全相同（允許 k=1 個 0），但翻轉版答案是 right - left + 1，刪除版是 right - left，差了 1。
理解測驗
🤔 nums = [1,1,1] 的答案為什麼是 2 而不是 3？
🤔 這題跟 Max Consecutive Ones III (k=1) 的程式碼差在哪裡？