leetcode 665. Non-decreasing Array

I. Topic effect

tag: greedy

https://leetcode.cn/problems/non-decreasing-array

Give you an integer array of length  n  nums , please judge whether the array can become a non-decreasing array with a change of at most 1 elementsequence.

We define a non-decreasing sequence like this: For any i (0 <= i <= n-2) in the array, nums[i] <=nums[i + 1].

Example 1:

Input: nums = [4,2,3]Output: true Explanation: You can do this by putting the first 4becomes 1 to make it a non-decreasing sequence.

Example 2:

Input: nums = [4,2,1]Output: false Explanation: You cannotChanges an element to a non-decreasing sequence.

Tips:

• n == nums.length

• 1 <= n <= 104

• -105 <= nums[i] <= 105

Second, problem-solving ideas

There is only one chance to modify a certain number at most, ask whether the array can be changed into a non-decreasing array.Example

Example 1: 4, 2, 3

Example 2:-1, 4,

2

, 3

Example 3: 2, 3, 3, 2, 4 When the following number is less than the previous number, for example, 2 in example 1 is less than 4, then you can modifyModify the preceding number to change 4 to 2 or modify the following number to change 2 to 4.We need to find this rule and determine which number to modify is actually related to the size of the previous number:

If the previous number does not exist, in example 1, there is no number in front of 4, we directlyModify the previous number to the current number 2;

If the previous number exists and is smaller than the current number, in example 2, we need to modify the previous number 4 to the current number 2;

If the previous number exists and is greater than the current number, in example 3, we need to modify the current number 2 to the previous number 3.

Because there is only one chance to modify, so use a variable cnt, initialize it to 1, after modifying the number, cnt will be decremented by 1. When you need to modify it next time, if cnt is 0, return false directly.Returns true after the traversal is complete.

Three, problem solving method

3.1 Java implementation

public class Solution {
public boolean checkPossibility(int[] nums) {
int cnt = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] < nums[i - 1]) {
if(cnt == 0) {
return false;
}
cnt--;
if (i == 1) {
nums[i - 1] =nums[i];
} else if (nums[i] >= nums[i - 2]) {
nums[i - 1] = nums[i];
} else {
nums[i] = nums[i - 1];
}
}
}
return true;
}
}


Four, Summary Notes

• 2022/7/31 The weather is very hot today