LeetCode 665. Non-decreasing Array
Created at 2017-11-03 Updated at 2017-11-07 Category LeetCode
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).
Explanation: You could modify the first
to get a non-decreasing array.
Explanation: You can not get a non-decreasing array by modify at most one element.
Note: The n belongs to [1, 10,000].
For this problem, We should count how many times the items of the array have been changed. So my idea is to compare
nums[i-1] and if
nums[i] < nums[i-1] then set
nums[i] . However the problem is not that easy, some conditions should take into consideration, for example
- Condition One:
nums[i] > nums[i-2]
nums[i] > nums[i-2], so replace
nums[i], that is
nums[i-1] = nums[i]
- Condition Two:
nums[i] < nums[i-2]
nums[i] < nums[i-2], so replace
nums[i-1], that is
nums[i] = nums[i-1]
As you can see, the key problem is which item should be replaced
nums[i-1] and what value should be set.