欢迎阅读 欢迎来到「最长连续递增序列」题解之旅本文将带你从“寻找数组中最长的连续上升段”这一直观需求出发深入理解贪心 一次遍历的简洁解法。在开始之前建议你先了解题目背景这是 LeetCode 674 题给定整数数组nums要求找出最长连续递增子序列的长度子序列元素在原数组中必须相邻。这与 LeetCode 300「最长递增子序列」不要求连续形成鲜明对比连续这一约束使得问题难度大幅降低只需一趟遍历即可解决。明确学习目标掌握如何用贪心 双指针或计数器统计连续递增段的长度理解为什么遇到nums[i] nums[i1]时重置计数器并熟练处理全等元素如[2,2,2]返回1等边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [1,3,5,4,7]输出3。本文将从问题分析、贪心遍历策略、计数器维护到代码实现层层递进。即使你对贪心算法还不熟悉我们也会从“一段一段数过去”的直觉出发让你轻松抓住核心思想——连续递增只需看相邻关系断了就重新开始。现在让我们一起在数组中找出最长的连续上升段吧 一、题目674. 最长连续递增序列 - 力扣LeetCode二、做题思路1. 问题分析前置分析本题要求返回数组中最长连续递增子序列的长度要求子序列中相邻元素严格递增且下标连续。由于必须连续问题简化为在数组中找最长的严格递增的连续段。2. 贪心策略核心决策规则使用滑动窗口双指针维护当前连续递增段left指向当前段的起始下标right指向当前段的结束下标开区间即当前窗口长度 right - left。从第二个元素开始遍历若nums[i] nums[i-1]说明递增延续right扩大窗口。否则递增中断更新全局最大长度并将窗口重置为从当前元素开始left i, right i1。遍历结束后再更新一次全局最大长度处理最后一段递增序列。3. 正确性说明简单版本由于要求子数组连续每个递增段都是独立的不存在跨段合并的可能性。因此只需在遍历过程中实时记录当前段的长度并在每个递增中断点比较更新答案。这种“分段统计”的策略能覆盖所有可能的连续递增段最终保留其中的最大值即为全局最长连续递增序列的长度。4. 实现细节边界防护数组长度n ≥ 1初始化left 0, right 1, count 0。当nums[i] nums[i-1]时right即可无需额外操作。当递增中断时先更新count max(count, right - left)再重置left i, right i 1。遍历结束后必须再次更新count因为最后一段递增段不会在循环内触发中断更新。5. 返回值目标映射返回count即最长连续递增子序列的长度。三、代码class Solution { public: int findLengthOfLCIS(vectorint nums) { int n nums.size(); // 滑动窗口双指针维护当前连续递增子数组的左右边界 // left窗口左边界起始下标 // right窗口右边界结束下标的后一位即当前窗口长度 right - left int left 0; int right 1; // 因为至少有一个元素初始窗口为 nums[0]长度1 int count 0; // 记录当前找到的最长连续递增长度 // 从第二个元素开始遍历 for (int i 1; i lt; n; i) { // 如果当前元素比前一个元素大说明递增序列延续右边界扩展 if (nums[i] gt; nums[i - 1]) { right; // 窗口长度增加 } else { // 否则递增序列中断更新最长长度并重置窗口从当前位置重新开始 count max(count, right - left); // 新窗口的左边界为当前元素的位置即 i右边界为 i1长度为1 left i; right i 1; } } // 最后一段递增子数组也需要统计 count max(count, right - left); return count; } };四、流程图五、正确性说明详细版本步骤 1符号与问题建模---------------------------------------------------- | 输入数组 nums长度 n | | 连续递增子序列相邻元素严格递增nums[i] nums[i1]| | 目标找到最长的连续递增段长度 | ---------------------------------------------------- | v ---------------------------------------------------- | 贪心策略双指针/滑动窗口 | | 从左到右扫描维护当前连续递增段的起始位置 left | | 和终止位置 right左闭右开区间 [left, right)。 | | 若 nums[i] nums[i-1]则 right 右移段延长 | | 否则段中断更新全局最大长度重置 left i, | | right i1从当前位置重新开始计数。 | | 贪心实质只要当前位置能延续递增就尽可能延长 | | 一旦中断就果断放弃当前段重新开始类似 | | “只要有利可图就继续无利则止损”的策略。 | ----------------------------------------------------设当前连续递增段的起始下标为left终止下标为rightright指向段尾的下一个位置段长度为right - left。遍历数组每遇到一个新元素检查它与前一个元素的大小关系若nums[i] nums[i-1]则递增关系成立当前段可延长right。否则递增中断当前段结束更新全局最大长度然后从i重新开始一个新的段left i,right i1。贪心选择性质在每一个连续的递增区间内贪心算法会将其完整地保留不会提前截断而在非递增位置贪心算法会立即终止当前段因为继续延伸已不可能连续性被破坏所以放弃是唯一合理选择。步骤 2关键性质 —— 分割与最优性反证法---------------------------------------------------- | 性质 1整个数组可以被分割成若干个极大的连续递增段| | 相邻段之间必有一个位置 i 满足 nums[i] nums[i1]。| | 每个极大段内部任意子段也都是连续递增的但 | | 极大段是该区域内最长的可能连续递增段。 | ---------------------------------------------------- | v ---------------------------------------------------- | 性质 2最优子段必为某个极大段 | | 任取一个连续递增子序列它必然完全落在某个极大段内。 | | 因为一旦跨过边界非递增位置连续性即被破坏。 | | 因此全局最长连续递增子序列的长度等于 | | 所有极大连续递增段长度的最大值。 | ---------------------------------------------------- | v ---------------------------------------------------- | 性质 3贪心扫描能准确识别所有极大段 | | 贪心算法在遇到非递增位置时立即分割不会遗漏任何边界| | 也不会把两个独立段错误合并因此它枚举了所有极大段。 | ----------------------------------------------------详细论证结合反证法反证假设假设存在一个最优连续递增子序列它跨越了两个相邻的极大段。根据定义相邻段之间必有一个位置i使得nums[i] nums[i1]那么该子序列若包含这两个位置的元素则必然不满足严格递增矛盾。因此任何连续递增子序列都完全包含在某个极大段内部。既然每个极大段内部所有元素都满足严格递增那么该段本身就是一个有效的连续递增子序列且其长度是段内所有可能子序列中最长的因为段内任意子段长度不超过段长。所以全局最优解只能是某个极大段的长度。贪心算法从左到右扫描每当nums[i] nums[i-1]时就判定当前极大段结束并在下一位置开始新的段。由于它不遗漏任何边界因为每次条件触发即分割且不错误合并只有严格递增时才延长所以它枚举出的段恰好就是全部极大连续递增段。因此贪心算法计算出的最大段长度即为全局最优解。步骤 3归纳证明 —— 扫描过程逐步逼近最大值---------------------------------------------------- | 初始设当前段为 [0,1)最大长度 maxLen 0。 | | 假设已经处理完前 i 个元素贪心算法正确维护了 | | 当前极大段的起始和长度并且 maxLen 已存储 | | 前 i 个元素中所有极大段的最大长度。 | ---------------------------------------------------- | v ---------------------------------------------------- | 处理第 i1 个元素 x nums[i] | | - 若 x nums[i-1]则当前段可延长right | | 此时当前段仍是极大段因为尚未遇到边界 | | maxLen 保持或等待最终更新。 | | - 否则当前段正式结束其长度为 right-left | | 更新 maxLen max(maxLen, right-left) | | 然后重置新段为 [i, i1)。 | | 归纳假设成立因为所有已结束的段都被记录。 | ---------------------------------------------------- | v ---------------------------------------------------- | 遍历结束后最后一段尚未更新再更新一次 | | maxLen max(maxLen, right-left)。 | | 最终 maxLen 即为所有极大段长度的最大值 | | 由性质 2 可知这就是最长连续递增子序列长度。 | ----------------------------------------------------详细论证归纳基础初始时left0, right1当前段长度为1maxLen0。此时尚未扫描任何元素段代表第一个元素正确。归纳步骤假设在处理到位置i-1时贪心算法已经正确识别了所有位于前i个元素中的极大段并已将其中最长长度保存在maxLen中且当前段[left, right)是尚未结束的当前极大段如果有。当扫描到nums[i]时若nums[i] nums[i-1]则当前段继续延伸无需更新maxLen因为段尚未结束。否则当前段在位置i-1处结束其长度为right-left更新maxLen然后新段从i开始lefti, righti1继续后续扫描。终止遍历完毕后最后一段可能未被更新因此额外更新一次确保所有段都被考虑。最终maxLen等于所有极大段长度的最大值由性质 2 可知这个最大值就是最长连续递增子序列的长度。 闭幕 恭喜你完成了「最长连续递增序列」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题要求连续递增与最长递增子序列可以不连续不同。代码中使用双指针left和right来记录当前连续递增段的起止。为什么遇到递减或相等时就要重置区间你能举例说明连续和不连续在遍历方式上的根本区别吗当nums[i] nums[i-1]时right指针向后移动表示当前区间可延长。否则计算当前区间长度并重置左指针。为什么重置时left right而不是left i注意right始终指向区间右端点的下一个位置如果数组全部递增如[1,2,3,4]left为0right最终为4长度为4如果全部递减如[4,3,2,1]每次都会重置最后count为1。代码能否正确处理长度只有1的数组可以for循环不执行最后count max(0,1-0)1本题要求严格递增nums[i] nums[i1]如果允许非递减即相等也算递增只需要将判断条件改成你会改吗改后[2,2,3]的结果会变成多少延伸挑战将题目改为最长连续递减序列只需修改哪个比较符号动手改一改并验证[3,2,1,4]的结果应为3。如果要求最长连续相同元素的长度即最长连续相等子数组如何修改判断条件如果你觉得本文对你有所帮助欢迎 点赞 / 收藏 关注作者获取更多题解 留言交流你的疑问或优化思路祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨
