从“值不值20万”到LeetCode 665：非递减数列数组调整策略详解

看到论坛里有位同行分享了自己的困境，差点把自己的职业发展路径给弄拧巴了：老婆在成都，他本人在广州，想结束异地生活，于是考虑放弃某新能源车企高级经理的职位，降级跳槽去成都，年薪预计会减少20万，正纠结值不值得。

咱们做技术的看问题，往往喜欢先算笔账。这20万是看得见的成本，但它更像一个压力测试。你在广州收入是高，但两地分居的那些隐性成本却很少被算进去——来回的机票高铁、频繁请假的时间、情绪内耗、吵架后的冷战与修复，这些“开销”可都不开发票。

如果真的决定去成都，关键在于把未来的条件谈明白：新岗位的成长性如何、未来有没有回升的通道、家庭内部关于住房和分工的计划。有时候，钱少一点不一定是亏损，日子顺了，整个系统的运行效率才会高，就像修复了一个恼人的内存泄漏，系统从此稳定流畅。

一道算法题引发的深夜“加班”：非递减数列

说到这，让我想起一道挺有意思的算法题——“非递减数列”。这道题我可太有印象了，算是有“心理阴影”。记得有次晚上十点，我都准备关电脑打游戏放松了，一个同事在群里突然冒出来一句：“东哥，数组这题我老是 Wrong Answer，你帮我看一眼？”得，就这一眼，直接看到了半夜十二点，游戏没打成，Bug 还坚挺地跑着呢。

先用大白话解释一下，啥叫“非递减数列”？简单说，就是对于一个数组 nums，从左到右它不能下降，必须满足 nums[i] <= nums[i+1]。题目通常会加一个限制条件：你最多只能修改一个元素的值，然后问你能不能通过这种“微调”，把整个数组变成非递减的。

这场景听起来像什么？好比你在整理一串同事的绩效评分，领导发话了：“你最多只能帮一个人‘润色’一下他的分数，看看能不能让后面的人不比前面的人差太多……”咳，就是个比方。

当时同事甩给我的测试数组是 [4, 2, 3]。肉眼一看就明白，把开头的 4 改成 2 或者 1，变成 [2, 2, 3]，这不就满足条件了嘛，感觉 so easy。但问题就出在写代码的时候，一紧张就容易瞎改。比如有的人一看到 nums[i] > nums[i+1]，想都不想就直接把 nums[i] = nums[i+1]，然后程序就“寄”了。

我当时的思路是，先别急着写，把“冲突”想清楚。所谓的冲突点，就是出现了 nums[i] > nums[i+1] 的情况。这里我们必须动手干预，要么改左边的 nums[i]，要么改右边的 nums[i+1]。而且，这种冲突在整个数组中最多只能出现一次，因为题目只允许你修改一个元素，出现两次或以上，你改一次是救不回来的。

核心的排查思路可以梳理成一条线：

1. 从左到右扫描一遍数组。
2. 每次发现 nums[i] > nums[i+1]，就记下来“已经发生过一次需要修改的情况了”。
3. 如果这是第二次发现冲突，那直接返回 False，没得救。
4. 如果是第一次冲突，就需要仔细想想，是该改前面这个数，还是改后面那个数。

很多人容易在第 4 步写迷糊。可以想象几种典型场景：

• 如果冲突发生在最开头，即 i == 0。这好办，前面没有其他元素限制，改左改右都行，通常为了省事，直接把 nums[i] 改小，让它等于 nums[i+1] 就行。
• 如果 nums[i-1] <= nums[i+1]，说明把夹在中间的 nums[i] 改成和 nums[i+1] 一样大是安全的，不会破坏 nums[i-1] 和新的 nums[i] 之间的顺序。
• 否则，如果 nums[i-1] 比 nums[i+1] 大，那么把 nums[i] 改小会破坏前面的顺序。这时只能选择把右边的 nums[i+1] 改大，让它至少等于 nums[i]。

边语音解释，我边敲了个 Python 函数，大致如下：

def can_be_non_decreasing(nums):
    """
    判断一个数组能不能通过最多修改一个元素，
    变成非递减数列
    """
    changed = False  # 标记有没有动过手

    for i in range(len(nums) - 1):
        if nums[i] <= nums[i + 1]:
            continue

        # 走到这里说明出现 nums[i] > nums[i+1]
        if changed:
            # 已经改过一次了，还撞上这种情况，直接GG
            return False

        changed = True

        # 决定改左边还是改右边
        if i == 0 or nums[i - 1] <= nums[i + 1]:
            # 改左边更安全：让当前值降下去
            nums[i] = nums[i + 1]
        else:
            # 否则只能把右边抬上来
            nums[i + 1] = nums[i]

    return True

这个代码里有两个细节，看着简单，都是踩过坑才记住的：
一个是 changed 这个标记变量，必须有。题目说“最多改一个”，如果你不记录，循环里每遇到一次冲突就改一次，那就成了“疯狂整容”，直接违规。
另一个是不要一上来就无脑改左边。我同事最初的版本是这样的：

if nums[i] > nums[i+1]:
    if changed:
        return False
    changed = True
    nums[i] = nums[i+1]

然后在测试数组 [3, 4, 2, 3] 上就翻车了。你可以手算一下：在 i=1 时发现 4 > 2，他把 4 改成 2，数组变成 [3, 2, 2, 3]；接着比较 3 > 2，又出现一次冲突，但修改机会已经用掉了，所以返回 False。可实际上，对于 [3, 4, 2, 3]，正确的处理方式是尝试把 2 改成 4（即 nums[2] = nums[1]），数组变为 [3, 4, 4, 3]，但最后一对 4 > 3 依然冲突，所以这个例子本就应该返回 False。这里关键在于，无脑改左边可能会“牵一发而动全身”，引发新的、本可避免的逆序。

后来我总结，写这种“最多允许一次修改”的题目，有个小套路：

• 用一个布尔变量记录是否已经“动过刀”。
• 每次发现不合法的地方，先冷静想想“这一刀下去，能不能同时解决当前和潜在的问题”。
• 如果发现了第二个不合法的地方，就可以毫不犹豫地返回 False。

也有人问，能不能不修改原数组？比如有些场景下你想保持原始数据不变。那可以简单点，先拷贝一份：

def can_be_non_decreasing_safe(nums):
    arr = nums[:]  # 浅拷贝一份
    return can_be_non_decreasing(arr)

当然，实际做题或面试时通常不用这么“矫情”，直接修改原数组就行，面试官一般不会在意这点改动。

写完用几个例子测试一下：

print(can_be_non_decreasing([4, 2, 3]))        # True
print(can_be_non_decreasing([3, 4, 2, 3]))     # False
print(can_be_non_decreasing([1, 2, 3, 3, 3]))  # True

结果同事在群里回了一句：“东哥，这不就是扫描一遍加个标记嘛？好简单哦。” 当时我真是哭笑不得，这种话听了，真想立刻把代码删了重写一遍，然后关电脑睡觉。

总之，这道题记住两个核心点就行：一是整个数组最多只允许出现一处“逆序”，多了肯定没救；二是当碰到这处逆序时，别急着下手，花一秒钟想清楚“是改左边更安全，还是改右边更稳妥”，就这多想的一秒，能帮你避开很多隐蔽的 Bug。

行了，关于职业选择和技术问题的讨论，在云栈社区总能找到一些有趣的视角和扎实的解法。我得去泡杯咖啡了，如果你有更好的写法或者不同的困惑，不妨也拿出来聊聊。