665. Non-decreasing Array

Question

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

Solution 1

记录两个最大值last1和last2，初始化为整数最小值。真值flag初始化为true用来记录是否已经有非单调递增的值出现。
遍历数组，如果当前数字num大于等于last2，则符合单调递增，更新last1和last2。

如果num小于last2，则不符合单调递增，此时将flag置为false。

• 如果num大于等于last1，则跳过现有的last2，将num保存在last2上。
• 如果num小于，则保留当前的last2

如果flag已经为false，则非单调递增的数字超过1个，返回false。
遍历完毕则返回true。

Code

class Solution {
    public boolean checkPossibility(int[] nums) {
        boolean flag = true;
        int last1 = Integer.MIN_VALUE, last2 = Integer.MIN_VALUE;
        
        for(int num : nums){
            if(num >= last2){
                last1 = last2;
                last2 = num;
            }
            else if(flag){
                flag = false;
                if(num >= last1) last2 = num;
                else continue;
            }
            else{
                return false;
            }
        }
        return true;
    }
}

Solution 2

原理和Solution 1相同，只不过采用单调栈的形式保存单调递增数字。

Code

class Solution {
    public boolean checkPossibility(int[] nums) {
        Stack<Integer> s = new Stack<>();
        boolean flag = true;
        
        for(int num : nums){
            if(s.isEmpty() || num >= s.peek()) s.push(num);
            else if(flag){
                flag = false;
                int temp = s.pop();
                if(s.isEmpty() || num >= s.peek()) s.push(num);
                else s.push(temp);
            }
            else{
                return false;
            }
        }
        return true;
    }
}