Leetcode 665 non decreasing array (greedy)

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.

We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

Example 1:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: nums = [4,2,1]
Output: false
Explanation: You can't get a non-decreasing array by modify at most one element.

Constraints:

• n == nums.length
• 1 <= n <= 104
• -105 <= nums[i] <= 105

Topic link ：https://leetcode.com/problems/non-decreasing-array/

The main idea of the topic ： Give an array , Change at most one number and ask if you can make it monotonous

Topic analysis ： When encountering a group of continuous decreasing , hypothesis nums[i] < nums[i - 1], There are two options ：

1. take nums[i] Bigger , The optimal solution to guarantee monotonicity is to nums[i-1] Assign to nums[i]

2. take nums[i-1] smaller , The optimal solution to guarantee monotonicity is to nums[i - 2] Assign a value to nums[i - 1], if i be equal to 1, The assignment is nums[i] that will do

You might as well choose the scheme first 2, After modification, you need to judge whether the modified value is less than or equal to nums[i], If not, only the scheme can be adopted 1, If there is a decline after that, it cannot be completed

0ms, Time beats 100%

class Solution {
    public boolean checkPossibility(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return true;
        }
        boolean change = false;
        for (int i = 1; i < n; i++) {
            if (nums[i] < nums[i - 1]) {
                if (!change) {
                    change = true;
                    int tmp = i - 2 >= 0 ? nums[i - 2] : nums[i];
                    if (tmp > nums[i]) {
                        nums[i] = nums[i - 1];
                    } else {
                        nums[i - 1] = tmp;
                    }
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}