各位题友大家好，今天是负雪明烛坚持日更的第 14 天。今天力扣上的每日一题是「665. 非递减数列」。

题目大意

给你一个长度为 n 的整数数组，请你判断在 最多 改变 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
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

数据范围

  • 1 <= n <= 10 ^ 4
  • - 10 ^ 5 <= nums[i] <= 10 ^ 5

解题思路

一、错误代码

拿到今天这个题，看到是个 Easy，就没有想太多了。直接判断是不是只出现了一次下降！迅速写出下面的代码，题目给的两个测试用例都通过了，那么就提交！

没想到，啪！直接来了个解答错误，很快啊！

  1. class Solution(object):
  2.     def checkPossibility(self, nums):
  3.         count = 0
  4.         N = len(nums)
  5.         for i in range(N):
  6.             if i > 0 and nums[i] < nums[i - 1]:
  7.                 count += 1
  8.         return count <= 1

题目说该代码没有通过测试用例 [3,4,2,3] 。仔细一想还真是，虽然该数组中只出现了一次下降，但是无论调整其中的一个数字都不能得到一个单调上升的数组。

那么，这题就有讲究了。下面我举了例子，相信我，下面的分析不难，你看完一定能懂。

二、举例分析

首先，看下面的几个测试用例，它们都因为数字 2 的出现，导致数组是非单调递增的。

  • 例①： 4, 2, 5
  • 例②： 1, 4, 2, 5
  • 例③： 3, 4, 2, 5

当数组中出现 2 时，破坏了数组的单调递增。为了让数组有序，我们需要对 2 或者 4 进行调整：

第①个用例，我们可以 把 4 调小到 <= 2 或者 把 2 调大到 4、5 ，使数组有序。

655-1.gif

第②个用例，我们可以 把 4 调小到 1、2 或者 把 2 调大到 4、5 ，使数组有序。
655-2.gif
第③个用例，我们必须 把 2 调大到 4、5，才能使数组有序：我们不能把 4 调整为一个 <= 2 的数字，因为 4 前面的元素是 3.

655-3.gif

三、归纳总结

当 nums[i] 破坏了数组的单调递增时，即 nums[i] < nums[i - 1] 时，为了让数组有序，我们发现一个规律（在上面三个例子中， nums[i] 都为 2， nums[i -1] 都为 4）：

  1. 如例①的情况，当 i = 1 ，那么修改 num[i- 1] ，不要动 nums[i] ，因为nums[i]后面的元素是啥我们还不知道呢，少动它为妙。
    2. 如例②的情况，当 i > 1 时，我们应该优先考虑把 nums[i - 1] 调小到 >= nums[i - 2] 并且 <= nums[i]。同样尽量不去修改 nums[i] ，理由同上。
    3. 如例③的情况，当 i > 1 且 nums[i] < nums[i - 2] 时，我们无法调整 nums[i - 1] ，我们只能调整 nums[i] 到 nums[i - 1] 。

代码

使用 Python2 写的代码如下。

  1. class Solution(object):
  2.     def checkPossibility(self, nums):
  3.         """
  4.         :type nums: List[int]
  5.         :rtype: bool
  6.         """
  7.         N = len(nums)
  8.         count = 0
  9.         for i in range(1, N):
  10.             if nums[i] < nums[i - 1]:
  11.                 count += 1
  12.                 if i == 1 or nums[i] >= nums[i - 2]:
  13.                     nums[i - 1] = nums[i]
  14.                 else:
  15.                     nums[i] = nums[i - 1]
  16.         return count <= 1

C++ 代码如下：

  1. class Solution {
  2. public:
  3.     bool checkPossibility(vector<int>& nums) {
  4.         int count = 0;
  5.         for (int i = 1; i < nums.size(); i++) {
  6.             if (nums[i] < nums[i - 1]) {
  7.                 if (i == 1 || nums[i] >= nums[i - 2]) {
  8.                     nums[i - 1] = nums[i];
  9.                 } else {
  10.                     nums[i] = nums[i - 1];
  11.                 }
  12.                 count ++;
  13.             }
  14.         }
  15.         return count <= 1;
  16.     }
  17. }

刷题心得

  1. 别小看 easy 题，它也能给我们带来收获，特别是easy题可能帮助我们练习某一种思路。
    2. 这题看分析那么一大截，其实只是当发现有下降的时候，多判断了一次 nums[i] 和 nums[i - 2]，本身没那么难。

欢迎加入刷题群

目前已经近 2000 人加入了每日一题打卡群。加入方式是通过每日一题打卡网站。每天都会同步力扣每日一题，这是个互相帮助、互相监督的算法题打卡网站，其地址是 https://www.ojeveryday.com/
【每日一题】665. 非递减数列 - 图4

想加入千人刷题群的朋友，可以复制上面的链接到浏览器，然后在左侧点击「加入组织」，提交力扣个人主页，即可进入刷题群。期待你早日加入。

也可点击 「阅读原文」，直接提交力扣个人主页。

关于作者

我是本文的作者是负雪明烛，毕业于北京邮电大学，目前就职于阿里巴巴。坚持刷算法题 5 年，共计刷了 800 多道算法题。做过的每个算法题都在 CSDN 上写题解博客，获得好评无数，CSDN 的累计阅读量已经 160万 次！博客地址是：https://blog.csdn.net/fuxuemingzhu
「每日算法题」公众号是我维护的一个算法题解公众号，主要讲解算法题的解法，也会分享找工作的经验。欢迎关注。
【每日一题】665. 非递减数列 - 图5

题目来源：839. 相似字符串组https://leetcode-cn.com/problems/similar-string-groups/