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

👋 欢迎阅读

🎯 欢迎来到「递增的三元子序列」题解之旅！本文将带你从“判断数组中是否存在三个递增元素”这一搜索问题出发，深入理解贪心算法的精巧应用，并掌握如何仅用两个变量在 O(n)O(n) 时间内完成判断。

在开始之前，建议你先：

• 了解题目背景：这是 LeetCode 334 题，给定整数数组nums，判断是否存在i<j<ki<j<k使得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(vector<int>& 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; } };

四、流程图