LeetCode 334：递增的三元子序列（贪心算法）—— 题解

欢迎阅读 欢迎来到「递增的三元子序列」题解之旅本文将带你从“判断数组中是否存在三个递增元素”这一搜索问题出发深入理解贪心算法的精巧应用并掌握如何仅用两个变量在 O(n)O(n) 时间内完成判断。在开始之前建议你先了解题目背景这是 LeetCode 334 题给定整数数组nums判断是否存在ijkijk使得nums[i]nums[j]nums[k]nums[i]nums[j]nums[k]。这是LIS最长递增子序列的简化版只需判断是否存在长度为 3 的递增子序列无需求出完整 LIS。明确学习目标掌握贪心 双变量追踪法维护当前最小的两个递增元素first和second理解为什么只需不断更新这两个变量即可判断三元组存在性。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [2,1,5,0,4,6]输出true。本文将从问题转化、贪心策略设计、双变量模拟过程到代码实现层层递进。即使你对贪心算法还不熟悉我们也会从“维护当前最小的第一个数和第二个数”这一直觉出发让你轻松抓住核心思想——只要不断更新最小前缀就能判断是否有更大的数在后面形成三元组。现在让我们一起在数组中寻找三个递增的“哨兵”解开递增三元子序列的贪心密码吧 一、题目334. 递增的三元子序列 - 力扣LeetCode二、做题思路1. 问题分析前置分析本题要求判断数组中是否存在长度至少为 3 的严格递增子序列。由于只关心是否存在不需要找到具体序列因此可以用贪心思想维护当前最小的两个候选值一旦遇到第三个比这两个都大的数即说明存在递增三元组。2. 贪心策略核心决策规则使用两个变量first表示当前找到的最小候选值即尽可能小的第一个元素。second表示当前找到的大于first的最小候选值即尽可能小的第二个元素。遍历数组按如下规则更新若x first则更新first x让第一个元素更小。否则若x second则更新second x让第二个元素更小。否则说明找到了一个比first和second都大的数返回true。3. 正确性说明简单版本first和second分别存储了当前所有递增二元组中的最小和次小值。每次遇到一个新数时若它比second还大则说明它能与之前的一对(first, second)组成递增三元组直接返回true。若x比first或second小则更新对应值为后续找到更小且更优的组合打基础。4. 实现细节边界防护初始化first nums[0]second INT_MAX表示尚未找到有效的第二小值。遍历从第一个元素开始依次按照上述规则更新。若遍历结束未返回true则不存在递增三元组返回false。5. 返回值目标映射若在遍历过程中满足条件直接返回true否则遍历结束返回false。三、代码class Solution { public: bool increasingTriplet(vectorint nums) { // 贪心策略维护当前遇到的最小值 a 和次小值 b // 一旦遇到大于 b 的数说明找到了长度为3的递增子序列。 // 初始化 // a 为第一个元素b 为 INT_MAX表示还未找到次小值 int a nums[0]; int b INT_MAX; // 遍历数组从第一个元素开始也可从第二个开始但当前代码从第一个开始 for (auto x : nums) { // 如果当前元素大于 a说明它可以作为第二个或第三个元素 if (x a) { // 如果当前元素还大于 b则说明已经找到 a b x 的三元组 if (x b) { return true; } else { // 否则当前元素介于 a 和 b 之间更新 b 为更小的次小值 b x; } } else { // 当前元素不大于 a即 a更新 a 为更小的最小值 a x; } } // 遍历结束仍未找到返回 false return false; } };四、流程图 闭幕 恭喜你完成了「递增的三元子序列」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题要求是否存在长度为 3 的递增子序列代码使用贪心维护两个变量a和b其中a是当前最小的“第一元素”b是当前最小的“第二元素”。为什么这样维护就能判断是否存在三元组你能用[2,1,5,0,4,6]手动模拟一下变量的变化过程吗当遍历到某个数x时如果x a我们尝试更新b如果x b则直接返回true。为什么不直接记录第三个数而要用a和b两个变量如果只用一个最小值min能判断出三元组吗代码中a初始化为nums[0]b初始化为INT_MAX。如果数组长度小于 3循环结束后返回false但题目保证长度至少为 1。如果nums全相等如[1,1,1]a和b如何变化最终返回什么如果数组元素范围很大正负均有代码中的比较符号是否仍然适用如果要求严格递增使用正确如果改为非递减只需改成你能快速调整吗延伸挑战将题目改为判断是否存在长度为 k 的递增子序列k 为任意正整数贪心法还能直接扩展吗你会如何维护一个数组来记录每个长度的最小末尾值提示参考“最长递增子序列”的贪心二分尝试将代码改为判断是否存在递减的三元子序列只需要修改哪些比较符号动手改一改。如果你觉得本文对你有所帮助欢迎 点赞 / 收藏 关注作者获取更多题解 留言交流你的疑问或优化思路祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨