665. Non-decreasing Array

拼搏现实的明天。 2022-06-03 05:52 89阅读 0赞

**题目描述：**

给定一个有n个整数的数组，检查它是否可以通过修改最多一个元素使它变得非递减数组

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).

--------------------

这道题看着很简单，但是AC率很低，那是因为没有想到全面的情形，比如我自己举了一个例子

5 8 7 9
    5 8 1 9

这两个都是到8的时候不满足升序了，但是前者是改变8，后者是改变1。

所以这道题难在当遇到nums\[i\] > nums\[i+1\]的时候，是把nums\[i\]降为nums\[i+1\] 还是将nums\[i+1\]升为nums\[i\].

如果可行的话，当然是选择优先把 nums\[i\]降为nums\[i+1\]，这样可以减少 nums\[i+1\] > nums\[i+2\] 的风险。

来看一下两种情况：

a. 1 3 5 4 6 7  --> 1 3 4 4 6 7
    
    　　　　当遇到5 > 4 的情况，这里因为4比5 之前的所有数字都大，所以可以把5 降为4。
    
    　b. 1 4 5 3 6 7  --> 1 4 5 5 6 7
    
    　　　　当遇到5 > 3 的情况，这里3比5之前的4小，所以没有选择，只能把3 升为5。

--------------------

代码：

package array;
    
    
    /*
    
    
                                    665. 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).
    
     */
    
    public class NondecreasingArray {
        public boolean checkPossibility(int[] nums) {
    
            int count = 0;
            for (int i = 0; i < nums.length-1; i++) {
                if (nums[i] > nums[i+1]){
                    count++;
                    if (i > 0 && nums[i + 1] < nums[i - 1]) nums[i + 1] = nums[i];
                    else nums[i] = nums[i + 1];
                }
            }
    
            return count <= 1;
        }
    
        public static void main(String[] args) {
    
            int[] nums = {
       3,4,2,3};
            System.out.println(new NondecreasingArray().checkPossibility(nums));
    
        }
    
    }