昨天第一次參加LeetCode Weekly Contest鸠窗， 一道題沒有做出來妓羊。所有時間都花在第一道題上了，被虐得很慘稍计。 看了一下別人的參考代碼躁绸，理解之后發(fā)現(xiàn)真的很簡單。
- Non-decreasing Array
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).
Example 1:
Input: [4,2,3] Output: True Explanation: You could modify the first 4 to1 to get a non-decreasing array.
Example 2:
Input: [4,2,1] Output: False Explanation: You can't get a non-decreasing array by modify at most one element.
Note: The n belongs to [1, 10,000].
首先在Array里面找到逆序的元素臣嚣，也就是nums[i] > nums[i + 1], 用reversOrder來記錄逆序的個數(shù)涨颜。如果個數(shù)超過1，則不可能通過改一個元素就變成正序茧球，所以返回false; 如果目前是第一個逆序，則討論兩種情況：
- nums[i - 1] <= nums[i + 1],比如[1,6,2,3,4]里6 > 2 并且5 > 2這種情況星持，要改正的話將6改成1或者2能滿足題意抢埋；但如果寫6改成2就可以同時包括i == 0的情況；
- nums[i - 1] > nums[i + 1], 比如[5,6,2,3,4]里6 > 2并且 5 > 2這種情況督暂，肯定是改2為6才能將此處的逆序改為正序揪垄。但這個例子的情況是改為[5,6,6,3,4]之后仍然有逆序，下次循環(huán)reverseOrder != 0也會返回false.
class Solution {
public boolean checkPossibility(int[] nums) {
int n = nums.length;
if (n <= 2){
return true;
}
int reverseOrder = 0;
for (int i = 0; i < n - 1; i++){
if (nums[i] > nums[i + 1]){
if (reverseOrder != 0){
return false;
} else {
if (i == 0 || nums[i - 1] <= nums[i + 1]){
nums[i] = nums[i + 1];
} else {
nums[i + 1] = nums[i];
}
reverseOrder++;
}
}
}
return true;
}
}
