LeetCode_贪心算法_中等_665.非递减数列

比眉伴天荒 2023-10-06 23:43 13阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

**给你一个长度为 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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/non-decreasing-array

## 2.思路 ##

（1）贪心算法  
本题参考[该 LeetCode 用户题解][LeetCode]。

## 3.代码实现（Java） ##

//思路1————贪心算法
    class Solution {
        
        public boolean checkPossibility(int[] nums) {
        
            int n = nums.length;
            if (n <= 2) {
        
                return true;
            }
            // cnt 记录改变元素的次数
            int cnt = nums[0] <= nums[1] ? 0 : 1;
            for (int i = 1; i < n - 1; i++) {
        
            	//遇到了递减的情况
                if (nums[i] > nums[i + 1]) {
        
                    //改变元素的次数加一
                    cnt++;
                    //如果次数超过 1，则在最多改变 1 个元素的情况下，该数组不能变成一个非递减数列
                    if (cnt > 1) {
        
                        return false;
                    }
                    /*
                    	还允许修改，但需要注意以下 2 点：
    					(1) 需要尽可能不放大 nums[i + 1]，这样会让后续非递减更困难；
    					(2) 如果缩小 nums[i]，但不破坏前面的子序列的非递减性；
    				*/
                    if (nums[i + 1] < nums[i - 1]) {
        
                        nums[i + 1] = nums[i];
                    } else {
        
                    	nums[i] = nums[i + 1];
    				}
                }
            }
            return true;
        }
    }

[LeetCode]: https://leetcode.cn/problems/non-decreasing-array/solution/yi-ding-yao-rang-ni-nong-dong-wei-shi-ya-u9te/