贪心算法 03

LeetCode 665

贪心算法

采用贪心算法的思想，每次只考虑三个连续的数，类似于滚动数组。

从总体来考虑，为了满足 "只改变一个数，使得数组为递增数组" 这个条件，所以原数组最多只能允许一组数 nums[i-1] > num[i]，用计数器 cnt 来记录。

从局部贪心的角度来考虑，如上所说，从左到右定义为 i - 2, i - 1, i 三个数，当出现 nums[i-1] > num[i] 则：

若 nums[i - 2] <= nums[i]，则可以做出的改变是：1. 让nums[i-1]变小 2. 让nums[i]变大，因为此时前面的数（i-1之前）已经满足了递增，所以为了不影响后面的判断，尽量让nums[i-1]变小。即：nums[i - 1] = nums[i]。不过鉴于数组长度可能小于等于2，所以滚动数组右边界的移动范围是 [1, n-1]，所以刚开始判断的时候会出现 i - 2 不存在的情况，把这个条件加上去就可以了。
除了上述的情况，其他队的情况都可以将 nums[i] 扩大，让nums[i] > nums[i - 2]，即 nums[i] = nums[i - 1]

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