[LeetCode] 665. Non-decreasing Array

Frank Chang
Sep 1, 2018 · 2 min read

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:

Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: [4,2,1]
Output: False
Explanation: You can't get a non-decreasing array by modify at most one element.

Note: The n belongs to [1, 10,000].


這題需要在最多只更改一個數字的情況下,該陣列數字是照順序遞增的,也就是不能有任一個數字比前面一個數字還小的情況…



解題思路:

首先因為最多有一次更改數字的機會,因此先設立一個 chance flag 來標記是否還有機會可以更改,另外再使用 max 記錄目前的最大值為何。

再來就用單層的 for 迴圈一一比較目前的數字 nums[i] 和下一個數字 nums[i+1],當發現 nums[i]nums[i+1] 還大的時候,就檢查 chance 是否為 false,如果為 false 就代表更改數字的機會已經用過了,此陣列不為一 non-decreasing array,可以直接回傳 false (line: 22 ~ 24);如果仍有更改數字機會的話,就視情況更新 nums[i]nums[i+1] 的值;此外,在每層迴圈都會將 max 與目前的數字 nums[i] 做比較,並適時更新 max 的值 (line: 27 ~ 29)

  • 如果下一個數字 nums[i+1] 比目前所記錄最大值 max 還大 (line: 13 ~14)

此時必須調整 nums[i] 的值:將 nums[i] 直接更新為 nums[n+1] 的值,代表我們將目前的數字調升/調降為跟下一個數字一樣的值以成為一 non-decreasing array

例如:

給定一初始陣列:[4, 2, 6, 9],在比較到 2, 6 時,此時 max 的值為:4,需將目前的數字調升為下一個數字:6,因此陣列會被更新為:[4, 6, 6, 9],在此迴圈結束後,max 的值也會順勢被更新為 6

  • 如果下一個數字 nums[i+1] 比目前所記錄最大值 max 還小 (line: 15 ~ 20):

此時必須調整 nums[i+1] 的值:取 nums[i]max 的最大值 (此時 max 尚未被更新,因此有可能會比 nums[i] 還來得小),將下一個數字調升為目前已解析數字中的最大值以成為一 non-decreasing array

例如:

給定一初始陣列:[3, 4, 1, 2],在比較到 4, 1 時,此時 max 的值為:3,需將下一個數字調升為 max(目前的數字, 目前所記錄的最大值)4,因此陣列會被更新為:[3, 4, 4, 2],在此迴圈結束後,max 的值也會順勢被更新為 6

如此,我們就可以在發現 nums[i]nums[i+1] 還大的時候,檢查 chance 是否為 false 來得知是否可以更新陣列或是直接判定不唯一 non-decreasing array 了。


Submission 結果:

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade