测试人社区

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

Example 1:

Input: [4,2,3]
Output: True
Explanation: You could modify the first
4 to 1

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

思路

从index=1开始遍历数组,判断nums[i]是否小于nums[i-1],如果小,就进行下面的更换:

  • i < 2 或者 nums[i] >= nums[i-2]:nums[i-1] = nums[i]
    • 4, 2, 5, 6 i = 1 -> 2, 2, 5, 6
    • 5, 8, 6, 9, 10 i = 2 -> 5, 6, 6, 9, 10
  • 否则:nums[i] = nums[i-1]
  • 4, 9, 3, 10 i = 2 -> 4, 9, 9, 10

java

class Solution {
    public boolean checkPossibility(int[] nums) {
        int count = 0;
        if (nums.length == 0) return false;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                count++;
                if (count > 1) return false;
            if (i - 2 < 0 || nums[i] >= nums[i-2]){
               nums[i-1] = nums[i];   
            }else
                nums[i] = nums[i-1];
        }
        
    }
        return true;
} 
}
import random
element = random.randint(10,10000)
element_str = str(element)
for j in range((len(element_str)-1)):
    if element_str[j] <= element_str[j+1]:
        print('True->the number is %d'%(element))
        break

可以用三个反引号格式化一下代码