2024-02-29|閱讀時間 ‧ 約 0 分鐘

滑動窗口應用: 刪掉一個元素之後,最長有幾個連續為1的子陣列_Leetcode 精選75題

題目敘述

題目會給定一個二元陣列nums(也就是說,陣列元素只有0,1這兩種情況)。

我們必須從裡面選擇一個元素刪除之後,請問連續為1的最長子陣列的長度是多少?

題目的原文敘述



測試範例

Example 1:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

刪除0,陣列變成[1,1,1]連續為1的最長子陣列長度為3

Example 2:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

刪除中間的那個0,陣列變成[1,1,1,1,1]連續為1的最長子陣列長度為5

Example 3:

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.
選擇刪除最左邊或最右邊的1,陣列變成[1,1]連續為1的最長子陣列長度為2

演算法

關鍵在於題目的要求是子陣列,而不是子序列。

子陣列一定要求必須連續。因此,最適合的演算法框架為滑動窗口sliding window


題目要求我們必須從裡面選擇一個元素刪除

接著建立一個起始點從0開始的滑動窗口,依序從左向右滑動

遇到第一個0,就先設定為被刪除的元素。

遇到第二個0,就收縮左邊界,直到離開第一個0為止


每次窗口滑動時,動態更新最長子陣列的長度


程式碼

class Solution:
def longestSubarray(self, nums: List[int]) -> int:
ans = 0
count0 = 0

l = 0
for r, num in enumerate(nums):

if num == 0:
# delete zero
count0 += 1

while count0 == 2:
# meet two 0s, update left boundary
if nums[l] == 0:
count0 -= 1
l += 1

ans = max(ans, r - l)

return ans

複雜度分析

分享至
成為作者繼續創作的動力吧!
從 Google News 追蹤更多 vocus 的最新精選內容從 Google News 追蹤更多 vocus 的最新精選內容

作者的相關文章

小松鼠的演算法樂園 的其他內容

你可能也想看

發表回應

成為會員 後即可發表留言
© 2024 vocus All rights reserved.