紅線的生存日誌

Problem 665: 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].

這個array 只容許一個數字的修改, 若改兩個以上就算是Fail

先設定一個變數可以儲存需要修改的次數, 也就是如果A[i] > A[i+1], 可以修改A[i] 也可以改 A[i+1]

如 [1,2,5,3] 就可以改5或改3

不過在某些Case 會遇到如果改了一個數字還是不行 [1,3,5,2,4]

即使改了2, 5也還是比4大

所以就要有一些限制

Solution By mark1990301

https://leetcode.com/problems/non-decreasing-array/discuss/106820/

bool checkPossibility(int* nums, int numsSize) {
    int count = 0, i = 0;
    for(i=0;i<numsSize-1;i++)
    {
        if (nums[i]>nums[i+1])
        {
            count++;
            if (count>=2)
                return false;
            if ( (i!=0 && i+2<numsSize && nums[i+2]<nums[i]) && 
                 (i-1>=0 && nums[i+1]<nums[i-1]) )
                return false;
        }
    }
    return true;
}

簡單說來就是, 一個一個比大, 如果後後個數字比現在的數字小, 後個數字又比前個數字小

有就會出現必須修改兩個數字的情況

結果後來看執行效率的情況, 竟然只有後8%(對LeetCode也可以比較你跟別人的執行時間, 殘酷阿...)

大家也太聰明了吧~~~~~

算了花好久時間了,之後真的很閒再來討論效率的問題吧、