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 first4
to1
to get a non-decreasing array.
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
A:
要记得修改nums的值。
class Solution { public: bool checkPossibility(vector<int>& nums) { nums.insert(nums.begin(),INT_MIN); nums.push_back(INT_MAX); int c = 0; for(int i =1;i<nums.size()-1; ++i){ if(nums[i] > nums[i+1] ){ // change at either i or i+1 c++; if(c>=2) return false; // now update nums[i] or nums[i-1] // every time, nums[i] >= nums[i-1] if(nums[i-1] > nums[i+1]) // now way to update at i nums[i+1] = nums[i]; // update at i+1 else nums[i] = nums[i+1]; } } return true; } };
要区分更改那种情况
No comments:
Post a Comment