AlgoNote 题解精讲：0665. 非递减数列（Non-decreasing Array）贪心判定与单点修正

教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇题解对应 AlgoNote 算法通关手册 题解库中的「0665. 非递减数列」标签数组难度中等。文章围绕能否在最多修改 1 个元素的条件下把数组变为非递减序列这一经典贪心判定问题展开先给出严谨的问题定义再推导单次遍历 计数 定点修正的求解思路逐行剖析参考代码并补充边界用例、复杂度分析与同类题目延伸。读完你既能独立写出可 AC 的checkPossibility也能掌握允许一次违规时如何通过局部修正而非全局重排来判定这类数组贪心题的通用套路。1. 题目还原与问题定义1.1 题目大意给定一个整数数组nums问能否在最多改变 1 个元素即最多修改数组中某一个位置上的值的条件下使整个数组变为非递减序列。如果能返回True否则返回False。非递减序列对于任意相邻下标i都满足nums[i] nums[i 1]。注意与严格递增的区别——相等元素是被允许的。最多改变 1 个元素既可以不改原数组已经非递减也可以只改一个位置改超过一个位置则不符合要求。这是 LeetCode 第 665 题在 题解总表 与 0600-0699 章节索引 中均可检索到对应条目是数组类贪心/模拟题的代表作。1.2 关键约束点修改元素指修改该下标处存储的整数值数组长度不变元素之间的相对顺序不变。修改后的元素值没有额外限制只要最终序列整体满足非递减即可例如可以把某个元素改成负数或任意整数只需满足相邻大小关系。2. 解题思路贪心计数 定点修正2.1 核心观察一逆序对的数量是判定的第一道门槛非递减序列不允许存在任何一对相邻逆序即不允许出现nums[i] nums[i 1]。由于一次修改最多只能影响两对相邻关系被修改元素与其左邻居、与其右邻居所以一旦数组中出现超过 1 处独立的nums[i] nums[i 1]逆序位置就无论如何不可能通过改 1 个元素修复。更进一步参考代码采用了更宽松的保守判定一旦逆序出现次数超过 1即 count 达到 2直接返回 False。说明此处计数策略取的是出现 2 次及以上即失败的安全边界。原文档的表述为这种情况出现超过 2 次则直接返回 False参考代码实际实现为count 1即返回False两种表述在至多允许 1 次逆序的意义上是等价的本文以参考代码为准。2.2 核心观察二一次逆序存在两种局部修正方案当发现唯一的逆序nums[i] nums[i 1]时为了让数组重新满足非递减只需把这对元素之一掰回合法区间有两种选择将nums[i]调低与左侧的nums[i - 1]持平将nums[i 1]调高与右侧的nums[i]持平。但方案 1 并不是总可行。设逆序位置为i若修改前nums[i - 1] nums[i 1]那么即使把nums[i]调低到与nums[i - 1]持平nums[i - 1]依然大于nums[i 1]即逆序并未被消除只是移动到了i-1与i1之间仍然非法。此时必须选择方案 2把nums[i 1]调高到与nums[i]持平。修改后关系变为nums[i - 1] nums[i] nums[i 1]因为nums[i - 1] nums[i 1]不成立即nums[i - 1] nums[i 1] nums[i]整段重新满足非递减。2.3 边界情况的隐含处理参考代码中修正动作带有一个前置条件if i 0 and nums[i - 1] nums[i 1]当i 0时逆序发生在数组头部左侧没有元素需要保护调高nums[1]到nums[0]即可条件不成立、无需修正也成立当逆序发生在尾部时循环最多遍历到len(nums) - 2不会越界当nums[i - 1] nums[i 1]时两种方案都可行代码不强制修正保持原值因为逆序已经存在且仅存在一次不需要真正落地修改即可判定成功。这正是贪心思路的精髓我们只关心能否判定成功而不必真的构造出修改方案因此代码只在必要时进行虚拟修正。3. 参考代码逐行解读以下为 non-decreasing-array.md 中给出的标准解法class Solution: def checkPossibility(self, nums: List[int]) - bool: count 0 for i in range(len(nums)-1): if nums[i] nums[i1]: count 1 if count 1: return False if i 0 and nums[i-1] nums[i1]: nums[i1] nums[i] return True3.1 执行流程拆解初始化计数器count 0记录已发现的相邻逆序个数。单次遍历for i in range(len(nums)-1)遍历所有相邻对(nums[i], nums[i1])无需处理最后一个元素。检测逆序若nums[i] nums[i1]则count 1。快速失败若count 1说明至少两处逆序改 1 个元素不可能修复立即return False。局部虚拟修正若i 0且nums[i-1] nums[i1]说明调低nums[i]无法根治将nums[i1]赋值为nums[i]模拟调高右邻居这一可行修正。遍历结束全程未触发快速失败返回True。3.2 为什么虚拟修正不影响后续判定修改后的nums[i1] nums[i]会参与后续nums[i1]与nums[i2]的大小比较。由于新值恰好等于左侧元素nums[i]而nums[i] nums[i2]若i2存在且没有产生新的逆序可被保证因此该修正只会降低后续产生新逆序的可能性绝不会引入新的逆序判定的正确性不受影响。3.3 复杂度分析时间复杂度O(n)。数组仅被完整遍历一次每次操作为常数时间其中n为数组长度。空间复杂度O(1)。仅使用一个计数器count无额外数据结构。4. 手推示例验证示例 1nums [4, 2, 3]i 04 2count 1i 0不进入修正分支。i 12 3无逆序。结果True把4调低为1或2即可例如[1, 2, 3]。示例 2nums [4, 2, 1]i 04 2count 1i 0不修正。i 12 1count 2 1直接return False。结果False。两处逆序改一个元素无法同时修复。示例 3nums [3, 4, 2, 3]i 03 4无逆序。i 14 2count 1i 1 0且nums[0]3 nums[2]2执行修正nums[2] 4数组变为[3, 4, 4, 3]。i 24 3count 2 1返回False。结果False。这里展示了修正发生在中部时仍需继续检查右侧相邻关系——这也是算法遍历而非提前终止于第一处逆序的原因。示例 4nums [-1, 4, 2, 3]i 14 2count 1nums[0]-1 nums[2]2无需修正。后续无逆序返回True把4调低为1即可如[-1, 1, 2, 3]。示例 5nums [5, 7, 1, 8]i 17 1count 1nums[0]5 nums[2]1修正nums[2] 7数组变为[5, 7, 7, 8]。后续无逆序返回True把1调高为7即可。5. 变式与易错点总结5.1 常见易错点只数逆序不修正仅统计逆序数量会误判示例 3 这类一次修正后又暴露新逆序的情况必须按规则执行虚拟修正再继续遍历。无脑调低nums[i]忽略nums[i-1] nums[i1]的情况会把调低左元素错误地当作可行方案导致漏判。忽略相等关系非递减允许判断逆序必须用而非。数组长度为 1 或 2len(nums)-1遍历天然覆盖空遍历与单次比较无需特判长度为 1 的数组恒为非递减直接返回True。5.2 思路的普适性本题属于允许 k 次修改的序列单调性判定家族核心方法论为找出所有违规相邻对统计数量是否超过可修复上限对每次违规按贪心策略做最小代价的局部修正优先选择不破坏其他关系的一侧修正后继续向后扫描若新的违规超出预算则失败。同样的相邻比较 计数模式在本仓库其他数组/序列题解中亦有体现可对照学习674. 最长连续递增序列对相邻元素大小关系的单次遍历判定、605. 种花问题贪心 相邻位置约束的可行性判定。6. 在仓库中的定位与延伸阅读本文所属章节数组题解目录 docs/solutions/0600-0699对应题解原文见 non-decreasing-array.md。数组基础概念线性表、连续存储、随机访问见 01_01_array_basic.md可帮助理解本题中修改数组元素 修改连续内存中某个下标的值这一操作的本质。题目难度为中等标签为数组在 00_05_solutions_list.md 题解总表中可按题号 0665 快速检索。若想系统学习相邻元素单调性相关算法可继续阅读 01_02_array_sort.md 及排序章节中关于非递减/递增判定与调整的讨论。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode-Go 题解 | 491. Non-decreasing SubsequencesDFS 回溯与双重 Map 去重求解非递减子序列LeetCode Go 题解 | 491. Non decreasing SubsequencesDFS 回溯与双重 Map 去重求解非递减子序列 导读 本文示例工程AlgoNote 题解精讲0491 非递减子序列——回溯 同层去重的完整实战解析AlgoNote 题解精讲0491 非递减子序列——回溯 同层去重的完整实战解析 本文基于「算法通关手册」AlgoNote 仓库中 0491. 非递减子序教程文档知识库如何用 Wand-Enhancer 免费解锁 WeMod 专业版新手 5 步完整指南如何用 Wand Enhancer 免费解锁 WeMod 专业版新手 5 步完整指南 周五晚上你打开一款新入手的单机大作准备在 WeMod 里调几个参数界桌面应用前端上一篇LunaTranslator终极游戏翻译解决方案三步跨越语言障碍下一篇music-metadata 项目推荐创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考