###### tags: `Leetcode` `medium` `array` `python` `c++`

# 665. Non-decreasing Array

## [題目連結:] https://leetcode.com/problems/non-decreasing-array/description/

## 題目:
Given an array ```nums``` with ```n``` integers, your task is to check if it could become non-decreasing by modifying **at most one element**.

We define an array is non-decreasing if ```nums[i] <= nums[i + 1]``` holds for every ```i``` (**0-based**) such that (```0 <= i <= n - 2```).

**Example 1:**

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

**Example 2:**

Input: nums = [4,2,1]
Output: false
Explanation: You cannot get a non-decreasing array by modifying at most one element.

## 解題想法:
* 此題為最多更改一個數字，使得整個數列為non-decreasing升序

* 想法:
* 考量當遍歷到nums[i]，因為不知道未來nums[i+1]....等
* **考慮與nums[i-1]關係**
* 對於nums[i-1]>nums[i]表示需要更改數字
* if i==1:
* 因為不知道未來nums[i+1]與nums[i]大小關係，所以安全起見需更改nums[i-1]值: **nums[i-1]=nums[i]**
* if nums[i-2]>nums[i]:
* 表示i>1，則需要考慮到nums[i]與nums[i-1]、nums[i-2]關係
* 因為前面nums[i-2]與nums[i-1]關係一定是升序nums[i-2]<=nums[i-1]了，所以安全起見需更改nums[i]值，**nums[i]=nums[i-1]**

## Python:

class Solution(object):
    def checkPossibility(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        #更改某數 使得數列為升序
        #考量當遍歷到nums[i] 因為不知道未來nums[i+1]....等
        #if i=1 :考慮與nums[i-1]
        #if i>1: 考慮與nums[i-1]、nums[i-2]關係
        count=0 #計算更改次數 
        for i in range(1,len(nums)):
            if nums[i]<nums[i-1]:
                count+=1
                if i==1 or nums[i-2]<=nums[i]:
                    nums[i-1]=nums[i] #將nums[i-1]改成nums[i]
                elif i>1 and nums[i-2]>nums[i]:
                    nums[i]=nums[i-1] #ex: 3 4 1
            if count>1:
                return False
        return True

nums = [4,2,3]
result=Solution()
ans=result.checkPossibility(nums)
print(ans)

## C++:

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int count=0, n=nums.size();
        if (n==1)
            return true;
        for (int i=1; i<n; i++){
            if (nums[i-1]>nums[i]){
                count+=1;
                if (count>1)
                    return false;
                if (i==1 || nums[i-2]<=nums[i])
                    nums[i-1]=nums[i];
                else
                    nums[i]=nums[i-1];
            }
        }
        return true;
    }
};