前往
大廳
主題

LeetCode - 1909. Remove One Element to Make the Array Strictly Increasing 解題心得

Not In My Back Yard | 2021-10-12 00:00:03 | 巴幣 0 | 人氣 226

題目連結:


題目意譯:
給定一索引值從 0 開始之整數陣列 nums,回傳真(True)如果藉由移除恰好一個元素便成為了嚴格遞增;反之,回傳假(False)。如果陣列已經是嚴格遞增,則回傳真。

陣列 nums 為嚴格遞增,如果 nums[i - 1] < nums[i] 對於每個索引值(1 ≦ i < nums.length)。

限制:
2 ≦ nums.length ≦ 1000
1 ≦ nums[i] ≦ 1000



範例測資:
範例 1:
輸入: nums = [1,2,10,5,7]
輸出: true
解釋: 藉由從 nums 移除索引值 2 的數字 10,其變為 [1,2,5,7]。
[1,2,5,7] 為嚴格遞增,所以回傳真。

範例 2:
輸入: nums = [2,3,1,2]
輸出: false
解釋:
[3,1,2] 為移除索引值 0 的元素之結果。
[2,1,2] 為移除索引值 1 的元素之結果。
[2,3,2] 為移除索引值 2 的元素之結果。
[2,3,1] 為移除索引值 3 的元素之結果。
沒有一個結果陣列為嚴格遞增,所以回傳假。

範例 3:
輸入: nums = [1,1,1]
輸出: false
解釋: 移除任何元素將得到 [1,1]。
[1,1] 不是嚴格遞增,所以回傳假。

範例 4:
輸入: nums = [1,2,3]
輸出: true
解釋: [1,2,3] 已經是嚴格遞增了,所以回傳真。


解題思維:
我們可以先掃過一次陣列 nums,如果我們發現有一次以上的索引值 i 滿足 nums[i - 1] >= nums[i](其中 i > 0),則代表我們不可能只移除一個元素就讓原數列變成嚴格遞增。因此此時回傳假。

而如果上述情況恰好只發生一次的話,我們可以試試看移除掉 nums[i - 1] 或是移除 nums[i] 看哪個可以讓數列變成嚴格遞增。如果都不行,就回傳假。

如果移除其中一者可行的話,有或是打從一開始原數列就是嚴格遞增的,則我們這時候回傳真。




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

創作回應

更多創作