[LeetCode] 665. Non-decreasing Array
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 結果:

