665. Non-decreasing Array

本文主要是介绍665. Non-decreasing Array，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

class Solution {
    public boolean checkPossibility(int[] nums) {        
        // corner case
        if(nums == null || nums.length <= 1) return true;
        
        // the count of continuous non-decreasing sub-array
        int count = 1;
        int index = 0;
        
        int n = nums.length;        
        for(int i = 1; i < n; i++){
            if(nums[i] < nums[i - 1]){
                index = i;
                count++;
            }
        }
        
        if(count == 1) return true;
        if(count == 2){ 
            // if the discord happens at start or end position, we can modify
            // it to match the condition
            if(index == 1 || index == n - 1) return true;
            
            // if in the middle, we modify nums[index - 2]
            // index - 2, (index - 1, index) , index + 1
            if(nums[index + 1] >= nums[index - 1] || nums[index] >= nums[index - 2]) {
                return true;
            }
            return false;
        }
        
        return false;
    }
}

https://leetcode.com/problems/non-decreasing-array/discuss/106826/JavaC%2B%2B-Simple-greedy-like-solution-with-explanation

用count来表示non decreasing的subarray的数量，如果是1直接return true，如果大于2直接返回false。

如果是2，说明是两段。分两种情况，第一种要求转折点index有index + 1 >= index - 1, 或者index >= index - 2.

这篇关于665. Non-decreasing Array的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！