LeetCode 665. Nondecreasing Array
撰写于 20171103 修改于 20171107 分类 LeetCode
Question
Given an array with n integers, your task is to check if it could become nondecreasing by modifying at most 1 element.
We define an array is nondecreasing 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 nondecreasing array.
Example 2:
Input: [4,2,1]
Output: False
Explanation: You can not get a nondecreasing array by modify at most one element.
Note: The n belongs to [1, 10,000].
Solution
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]
with nums[i1]
and if nums[i] < nums[i1]
then set nums[i1]
with nums[i]
. However the problem is not that easy, some conditions should take into consideration, for example
 Condition One:
nums[i] > nums[i2]


Here nums[i] > nums[i2]
, so replace nums[i1]
with nums[i]
, that is nums[i1] = nums[i]
 Condition Two:
nums[i] < nums[i2]


Here nums[i] < nums[i2]
, so replace nums[i]
with nums[i1]
, that is nums[i] = nums[i1]
As you can see, the key problem is which item should be replaced nums[i]
or nums[i1]
and what value should be set.
Accepted Code

