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].

?

要完成的函數：

bool checkPossibility(vector<int>& nums)?

?

說明：

1、這道題目給定一個vector，要判斷這個vector至多改變一個元素的值之后，是不是變成了非減序列。

首先筆者想的是，比如序列[1,4,2,3]，這個序列改變4的值也就可以了，這樣子的序列中間必然會有一個凸起，4就是這個凸起。

那我們可以先找到這個凸起，從前往后找跟從后往前找，如果只有一個凸起的話，那么就接著判斷，如果有多個凸起，那么必定不能只改一個元素。

部分代碼如下：

        int s1=nums.size();int i=0,j=s1-1;while(i<s1-1){if(nums[i]<=nums[i+1])i++;elsebreak;}if(i==j)//當整個序列非降序排列return true;while(j>i){if(nums[j]>=nums[j-1])j--;elsebreak;}if((j-1)!=i)//如果中間有多個元素return false;    

這樣子就記錄了i和j的值。

?

2、當確實只有一個凸起時，我們進行下一步判斷。

還是以上面提到的序列為例子，[1,4,2,3]，i=1，j=2，這個凸起的形成是由于nums[i]>nums[j]，那我們可以改i這一位的值，也可以改j這一位的值，使得nums[i]<=nums[j]。

怎么判斷什么時候要改i的值，什么時候要改j的值？

?

比如[3,4,2,5]，i=1，j=2，這時候由于nums[i]的前一位3，大于nums[j]=2，所以我們只能修改j這一位的值，而不能修改i這一位的值。

那如果nums[i]的值，還是比nums[j]的下一位大呢，這時候我們就算修改j這一位的值，修改完也不能形成非減序列，這時候就要返回false。

如果nums[i]的值，小于等于nums[j]的下一位，那這時候就要返回true了。

?

還有另一種情況，如果nums[i]的前一位，小于等于nums[j]，比如上面提到的[1,4,2,3]，i=1，j=2，那這時候我們就可以修改i的值了，直接返回true即可。

代碼如下：

        if(i!=0){if(nums[i-1]>nums[j])//只能改j這一位
            {if(j==s1-1)return true;if(nums[i]>nums[j+1])return false;return true;}elsereturn true;}return true;//如果i==0，那么直接修改nums[i]的值就可以了

上述代碼雖然考慮的過程繁瑣了點，但是實測38ms，beats 86.96% of cpp submissions，效果還是可以的。

?

3、附上完整代碼，分享給大家，如下：

    bool checkPossibility(vector<int>& nums) {int s1=nums.size();int i=0,j=s1-1;while(i<s1-1){if(nums[i]<=nums[i+1])i++;elsebreak;}if(i==j)return true;while(j>i){if(nums[j]>=nums[j-1])j--;elsebreak;}if((j-1)!=i)return false;if(i!=0){if(nums[i-1]>nums[j])//只能改j這一位
            {if(j==s1-1)return true;if(nums[i]>nums[j+1])return false;return true;}elsereturn true;}return true; }

?