前往
大廳
主題

LeetCode - 1493. Longest Subarray of 1's After Deleting One Element 解題心得

Not In My Back Yard | 2024-03-14 12:00:22 | 巴幣 200 | 人氣 47

題目連結:


題目意譯:
給定一個二元陣列 nums,你需要從中刪除一個元素。

回傳結果陣列中只包含 1 的最長非空子陣列之大小。如果不存在著這樣子的子陣列,則回傳 0。

限制:
1 ≦ nums.length ≦ 10 ^ 5
nums[i] 只會是 0 或是 1。



範例測資:
範例 1:
輸入: nums = [1,1,0,1]
輸出: 3
解釋: 將位於位置 2 的數字刪除後,[1,1,1] 包含 3 個 1。

範例 2:
輸入: nums = [0,1,1,1,0,1,1,0,1]
輸出: 5
解釋: 將位於位置 4 的數字刪除後,[0,1,1,1,1,1,0,1] 中只包含 1 的最長子陣列為 [1,1,1,1,1]。

範例 3:
輸入: nums = [1,1,1]
輸出: 2
解釋: 你必須刪除一個元素。


解題思維:
假設現在知道對於每一個位置 i,我們都知道其往左看可以看到幾個連續的 1(只要看到 0 便停止,可以參見這題的「延伸」一詞,不過本題中不包含「自己」)、往右可以看到幾個連續的 1。假設這兩個數值分別是 Li 和 Ri,則所求即為所求位置 i 的 Li + Ri 之值中的最大值。

因此我們只要先由左至右掃過一次求出每個位置的 Li 值,再由右至左掃過一次求出每個位置的 Ri 值。最後再掃一次根據上面的方式求出所求即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作