Every day a Leetcode

题目来源：665. 非递减数列

解法1：贪心

本题是要维持一个非递减的数列，所以遇到递减的情况时（nums[i] > nums[i + 1]），要么将前面的元素缩小，要么将后面的元素放大。

但是本题唯一的易错点就在这：

如果将 nums[i] 缩小，可能会导致其无法融入前面已经遍历过的非递减子数列；
如果将 nums[i + 1] 放大，可能会导致其后续的继续出现递减；

所以要采取贪心的策略，在遍历时，每次需要看连续的三个元素，也就是瞻前顾后，遵循以下两个原则：

需要尽可能不放大 nums[i + 1]，这样会让后续非递减更困难；
如果缩小 nums[i]，但不破坏前面的子序列的非递减性；

算法步骤：

遍历数组，如果遇到递减：

还能修改：
修改方案1：将 nums[i] 缩小至 nums[i + 1]；
修改方案2：将 nums[i + 1] 放大至 nums[i]；
不能修改了：直接返回false；

代码：

/** @lc app=leetcode.cn id=665 lang=cpp** [665] 非递减数列*/// @lc code=start
class Solution
{
public:bool checkPossibility(vector<int> &nums){if (nums.size() <= 2)return true;int n = nums.size();bool flag = nums[0] <= nums[1] ? true : false; // 标识是否还能修改// 遍历时，每次需要看连续的三个元素for (int i = 1; i < n - 1; i++){if (nums[i] > nums[i + 1]) // 出现递减{if (flag) // 如果还有修改机会，进行修改{if (nums[i + 1] >= nums[i - 1]){ // 修改方案1：将nums[i]缩小至nums[i + 1]nums[i] = nums[i + 1];}else{ // 修改方案2：将nums[i + 1]放大至nums[i]nums[i + 1] = nums[i];}flag = false; // 用掉唯一的修改机会}else // 没有修改机会，直接结束return false;}}return true;}
};
// @lc code=end

结果：

在这里插入图片描述

复杂度分析：

时间复杂度：O(n)，其中 n 是数组 nums 的长度。

空间复杂度：O(1)。

解法2：数组

在这里插入图片描述

代码：

class Solution
{
public:bool checkPossibility(vector<int> &nums){int n = nums.size();for (int i = 0; i < n - 1; i++){int x = nums[i], y = nums[i + 1];if (x > y){nums[i] = y;if (is_sorted(nums.begin(), nums.end())){return true;}nums[i] = x; // 复原nums[i + 1] = x;return is_sorted(nums.begin(), nums.end());}}return true;}
};