665. Non-decreasing Array [Easy]

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

Given an array nums 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 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. (actually change 4 to 2 is fine too)

Example 2:

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

Constraints:

1 <= n <= 10 ^ 4- 10 ^ 5 <= nums[i] <= 10 ^ 5

---

算法思路：

先找一个一个不满足的i，记为index，找不到说明愿数组满足要求，返回true；找到，记为index，将index的nums值改为index+1的nums值，判断是否满足，满足返回true；不满足，将index+1的nums值改为index的nums值，判断是否满足，满足返回true，不满足这里直接返回false；注意，以上操作最终要还原原数组nums，避免对原数组的修改This question is not Easy，cause there are exist duplicate elements，Medium is reasonable. // O(n) O(1) class Solution { public: bool checkPossibility(vector<int>& nums) { bool modified = false; int n = nums.size(); int index; int indexOfNumsVal; for (int i = 0; i < n - 1; i++) { if (nums[i] > nums[i + 1]) { modified = true; index = i; break; } } if (!modified) return true; // modified nums[index] = nums[index + 1] and judge indexOfNumsVal = nums[index]; nums[index] = nums[index + 1]; bool res = true; for (int i = 0; i < n - 1; i++) { if (nums[i] > nums[i + 1]) { res = false; break; } } nums[index] = indexOfNumsVal; // Restore the array to its original state if (res) return res; // modified nums[index + 1] = nums[index] and judge indexOfNumsVal = nums[index + 1]; nums[index + 1] = nums[index]; res = true; for (int i = 0; i < n - 1; i++) { if (nums[i] > nums[i + 1]) { res = false; break; } } nums[index + 1] = indexOfNumsVal; // Restore the array to its original state return res; } };

优化循环过程，使得一次循环搞定 

// O(n) O(1) class Solution { public: bool checkPossibility(vector<int>& nums) { int modified = 0; int n = nums.size(); int index; int indexOfNumsVal; for (int i = 0; i < n - 1; i++) { if (nums[i] > nums[i + 1]) { modified++; if (modified == 1) { if (i > 0 && nums[i - 1] > nums[i + 1]) { // 有前驱，且前驱比后继大，把后继改成i处的数值 index = i + 1; indexOfNumsVal = nums[i + 1]; nums[i + 1] = nums[i]; } else { // 没前驱，或者后继大于等于前驱，把i处的数值改成后继值 index = i; indexOfNumsVal = nums[i]; nums[i] = nums[i + 1]; } } else if (modified == 2) { nums[index] = indexOfNumsVal; return false; } } } if (modified > 0) nums[index] = indexOfNumsVal; return true; } };