关于leetcode:leetcode-665-Nondecreasing-Array-非递减数列中等

3次阅读

共计 1006 个字符，预计需要花费 3 分钟才能阅读完成。

标签: 贪婪

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

给你一个长度为 n 的整数数组 nums，请你判断在最多扭转 1 个元素的状况下，该数组是否变成一个非递加数列。

咱们是这样定义一个非递加数列的：对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

示例 1:

输出: nums = [4,2,3]
输入: true
解释: 你能够通过把第一个 4 变成 1 来使得它成为一个非递加数列。

示例 2:

输出: nums = [4,2,1]
输入: false
解释: 你不能在只扭转一个元素的状况下将其变为非递加数列。

提醒：

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

最多只有一次批改某个数字的机会，问是否将数组变为非递加数组。举例

例 1:4， 2，3

例 2:-1，4，2，3

例 3:2，3，3， 2，4
当前面的数字小于后面的数字后，例如例 1 中的 2 小于 4，这时能够将批改后面的数字将 4 批改为 2 或批改前面的数字将 2 改为 4。咱们须要找到这个法则，判断批改哪个数字其实跟再后面的一个数大小有关系：

如果再后面的数不存在，例 1 中，4 后面没有数字了咱们间接批改后面的数字为以后数字 2 即可；

如果再后面的数字存在，并且小于以后数字时，例 2 中，咱们须要批改后面的数字 4 为以后数字 2；

如果再后面的数字存在，且大于以后数，例 3 中，咱们须要批改以后数字 2 为后面的数 3。

因为只有一次批改的机会，所以用一个变量 cnt，初始化为 1，批改数字后 cnt 自减 1，当下次再须要批改时，如果 cnt 为 0，间接返回 false。遍历完结后返回 true。

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;
    }
}