最近在复盘一些经典的数组类算法题时我重新把“递增三元子序列”这道题翻了出来。这道题本身不复杂但它刚好卡在一个很有意思的位置比暴力上了一个台阶又不像动态规划那样需要大动干戈刷题入门和解法演进都能从中找到价值。而更让我在意的是在agent工程化和实时链路处理逐渐普及的今天这种看似基础的算法思路其实藏着一套很典型的工程化思维模式。这篇笔记我会按自己的习惯来写先追一遍从朴素到最优的解法演进讲清楚每一步“为什么这么做”然后从工程落地视角拆解代码如何组织、接口如何设计、边界如何处理最后结合流式计算场景说说这类逻辑是怎么被改造成可运行的工程模块的。1. 问题本身一道题背后藏着什么1.1 题意与第一反应题目描述很简洁给定一个整数数组判断数组中是否存在长度为3的递增子序列要求满足 i j k 且 nums[i] nums[j] nums[k]。注意这里说的是子序列不需要连续只要下标严格递增就行。返回布尔值。我第一次见到这题时第一反应肯定是三重循环直接扫。三层循环枚举 i、j、k判断条件是否成立。这个解法没有任何思考成本代码也很简单但复杂度是 O(n^3)数组长度稍微上去一点比如上万级别基本就跑不动了。如果面试现场只给出这个方案大概率会被追问一句“能不能优化”这里其实已经触及了这类题的核心考察点你愿不愿意从“枚举所有可能”的惯性里跳出来去找那些“不需要枚举完整组合”就能得出结论的信息。1.2 暴力的局限与优化的起点暴力的本质是把所有可能的三元组都验证一遍。但仔细想想真正需要验证的并不是所有组合。我们要找的是一个“中间值”以及大于它的右侧值同时还要保证左侧存在更小值。这意味着如果我在遍历到某个位置 j 时已经知道“左侧最小值”和“右侧最大值”那就只需要一次 O(1) 的判断就能确定以 j 为中间元素是否可行。这个思路就是典型的用预处理信息换时间。类似的做法在很多数组题里都出现过比如前缀和、前缀最值、后缀最值。它们的作用都是把重复计算的信息提前算好让后续判断变得更轻。所以优化的起点不是“少循环一层”而是“改变信息的获取方式”。从枚举组合变成对每个中间位置做条件判定。2. 解法演进从 O(n^3) 到 O(n) 的两次关键跳跃2.1 中间值枚举用空间换时间基于上面的思路可以先写一版 O(n) 时间、O(n) 空间的解法。这里用两个辅助数组leftMin[i] 表示 nums[0..i] 的最小值rightMax[i] 表示 nums[i..n-1] 的最大值。然后在每个 j从 1 到 n-2上检查是否满足 leftMin[j-1] nums[j] rightMax[j1]只要有一个位置成立就说明存在递增三元组。def increasing_triplet_prefix(nums): n len(nums) if n 3: return False left_min [0] * n left_min[0] nums[0] for i in range(1, n): left_min[i] min(left_min[i - 1], nums[i]) right_max [0] * n right_max[n - 1] nums[n - 1] for i in range(n - 2, -1, -1): right_max[i] max(right_max[i 1], nums[i]) for j in range(1, n - 1): if left_min[j - 1] nums[j] right_max[j 1]: return True return False这个版本逻辑很清晰而且不容易出错。它把原来 O(n^3) 的枚举拆成了三次 O(n) 遍历。代价是额外使用了两个长度 n 的数组空间复杂度 O(n)。工程上如果对内存不敏感这个做法完全够用。但题目通常会追问能不能把空间也省下来于是就有了下一个版本。2.2 贪心双变量状态压缩到极致真正的经典解法是维护两个变量一边遍历一边更新。我习惯把它们命名为 first 和 second分别表示“当前遇到过的最小值”和“比 first 大的次小值”。遍历每个数字 num 时按以下顺序更新如果 num first则更新 first num。否则如果 num second则更新 second num。否则说明 num first 且 num second由于 first second 一定成立所以 num 可以和 first、second 构成递增三元组直接返回 True。代码很短但第一次看到的人往往会有两个疑问为什么更新 first 不会破坏前面的“潜在组合”为什么数字等于 first 或 second 时要使用 而不是 def increasing_triplet(nums): first float(inf) second float(inf) for num in nums: if num first: first num elif num second: second num else: return True return False这个解法的时间复杂度 O(n)空间复杂度 O(1)。从面试角度说这基本算是最优解了。2.3 为什么双变量是对的直觉与严谨性先解答第一个疑问。更新 first 为更小的值表面上看像是“丢掉了之前的候选”实际上不会丢失任何可能的三元组。因为三元组要求 i j k而 first 只是用来充当“三元组中的最小值”的。如果后面出现一个比当前 first 更小的值那么用它作为最小值能让后续“大于 first 的数”门槛更低更容易找到第二和第三个数。严格一点说这其实是一种贪心策略我们希望每一个位置上的“候选最小值”尽可能小这样后面的元素更容易形成递增关系。second 也是一样在保证 first second 的前提下second 越小越容易找到第三个数。() 关于等于号如果允许重复元素题目要求严格递增所以当 num first 时不能把 num 作为“大于 first 的 second”只能更新 first当 num second 时同理。如果误用 代替 遇到数组 [2, 2, 3] 这种场景second 可能被错误地更新成 2导致最终结果错误。细节就在这个等号里。为了更直观验证贪心的正确性可以举一个例子数组 [5, 1, 6, 2, 7]。遍历到 6 时first1second6实际上是 first1second5 后被 6 更新这里不展开读者可以自行模拟。总之到 7 时7 second返回 True。表面上 5、6、7 是一组但由于中途把 first 更新成了 1实际判断用的是 1、6、7 或 1、2、7结论不受影响因为题目只要求“存在”不要求输出具体组合。这段演进的本质是从“完整枚举”到“局部信息判断”再到“状态压缩”。每一步都是在减少无用计算和信息冗余这也是很多数组类最优解的共同套路。3. 工程化视角好代码不只是“AC”3.1 命名的力量从 first/second 到 minVal/midVal刷题时用 first、second 没问题但放进工程代码里这两个变量名很容易让人困惑。first 是什么第二什么看代码的人需要从上下文反推语义这是在增加认知负担。我在实际落地时更倾向于用 minVal、midVal 这种自解释命名。minVal 表示“当前已遍历区间内的最小值”midVal 表示“能找到一个左侧更小值的、在当前已遍历区间内的中间候选值”。这样即使不看注释代码的意图也基本能读出来。def has_increasing_triplet(nums): min_val float(inf) mid_val float(inf) for num in nums: if num min_val: min_val num elif num mid_val: mid_val num else: return True return False命名看起来是小事但如果说这道题要“工程化”第一步就是把这种面向解法的命名改成面向语义的命名。代码首先是给人看的其次才是给机器执行的。3.2 封装与接口设计把算法变成组件真正工程化时一个函数不应该只是“判断一下返回布尔值”。要考虑的问题包括入参合法性传 None、空数组、长度为 2 的数组都要有明确行为。返回语义返回 True/False 很直接但某些调用方可能需要三元组本身或者需要知道“是否存在且从哪个位置开始”。多态与复用如果以后要判断四元、五元子序列代码能不能平滑扩展一个更完整的封装会考虑把“寻找递增 K 元子序列”抽象成通用方法。下面这个版本用贪心数组维护 K-1 个候选值import bisect def has_increasing_k(nums, k): if not nums or k 1: return False tails [] for num in nums: pos bisect.bisect_left(tails, num) if pos len(tails): tails.append(num) else: tails[pos] num if len(tails) k: return True return False这段代码实际上是参考了最长递增子序列LIS的贪心数组维护法。bisect_left 会找到第一个大于等于 num 的位置保证序列严格递增。如果最终长度达到 k说明存在长度为 k 的递增子序列。相应的递增三元子序列就是 k3 的特例只是我们手写两个变量避免引入数组和二分依赖。工程中如果确定只需要三元双变量版更轻、更省。如果需求可能扩展用 K 元版更省心。3.3 测试与边界用例设计工程化绕不开测试。这道题的边界情况很值得整理成一张表我平时做代码评审时也会让同事先列这些用例用例输入期望结果说明空数组[]false长度不足单元素[1]false长度不足双元素[1,2]false长度不足普通命中[1,2,3,4]true最直观场景逆序数组[4,3,2,1]false不可能存在含重复元素[2,2,3,4]true严格递增2 3 4重复元素干扰[2,2,2]false必须严格递增大值在前[5,1,5,2,5]false第一次更新 first 后无后续更大值最小值和中间值交叉出现[3,1,4,2,5]true1,2,5 满足条件特别是 [5,1,5,2,5] 这个用例很多人会误判成 true实际上数组里不存在严格递增的 i j k 使得 nums[i] nums[j] nums[k]。1 2 5 是存在的因为下标 1、3、4 对应 1、2、5且 1 2 5所以这个用例应该是 true。读者自己模拟一下就会发现这个用例并不反直觉反而说明了“更新 first 不会丢失后续机会”。3.4 参数选择与复杂度定位还有一个工程中容易被忽略的问题这个算法到底运行多快双变量版本每次迭代只做常数次比较10 亿级别的数据也能在秒级跑完以 Python 的常规性能估算会慢一些但 C/Java 没问题。这个复杂度定位很重要因为它意味着可以放心在实时链路的每个元素上调用不需要额外聚合或批处理。4. 当“工程化”遇上实时系统从刷题到流计算4.1 agent 的工程化算法如何被服务化调用最近讨论比较多的是 agent 的工程化。一个算法写在笔记本里能跑不代表它能被稳定地接进 agent 的工作流。agent 场景下你往往需要把“判断是否出现递增三元组”这样的小能力封装成一个内部工具或函数对外提供清晰入参出参对内保证无状态、可重入、可超时。双变量版这个算法非常适合这类场景。因为它是纯函数、无状态进入时只维护两个变量调用完成后不留下任何外部副作用。把它发布成一个 HTTP 接口、消息队列的消费者函数或者 agent 里的一个 tool都非常自然。我见过一些工程化实践会把这类判断逻辑包一层“策略模式”后面再接一个事件回调。效果就是当算法判定存在递增三元组时系统自动触发一个后续动作比如告警、推荐或数据标记。这已经脱离了“刷题”范畴变成了业务规则引擎的一部分。4.2 flink 场景下的“上升三元组”检测这里不得不提一下工程化的 flink 代码。流式计算里经常有“检测连续上升趋势”的需求比如监控系统在一段时间内发现 CPU 使用率出现了至少三次阶梯式上升就会触发扩容或告警。这类需求二进制上就是一个递增三元子序列检测但流式环境比离线数组要复杂得多。离线版本输入是一个定长数组可以直接随机访问。流式版本输入是无穷无尽的不知道下一个元素什么时候来也不知道整体长度。在 flink 里实现思路有两种第一种是使用状态编程。在 KeyedProcessFunction 里维护 minVal 和 midVal 状态每条数据到来时更新状态并判断。注意要给状态设置 TTL避免长时间不满足条件时状态无限增长。另一种思路是基于 CEP复杂事件处理通过定义 pattern 来描述“第一个值 第二个值 第三个值”的复合事件。CEP 更符号化也更容易表达业务语义但底层实现仍然会涉及类似的状态维护。如果要用 flink 状态编程实现大概的逻辑骨架长这样示意代码需要根据实际版本调整public class TripletDetectFunction extends KeyedProcessFunctionString, Integer, Boolean { private ValueStateInteger minState; private ValueStateInteger midState; Override public void open(Configuration parameters) { ValueStateDescriptorInteger minDesc new ValueStateDescriptor(min, Integer.class); ValueStateDescriptorInteger midDesc new ValueStateDescriptor(mid, Integer.class); minState getRuntimeContext().getState(minDesc); midState getRuntimeContext().getState(midDesc); } Override public void processElement(Integer value, Context ctx, CollectorBoolean out) throws Exception { Integer minVal minState.value(); Integer midVal midState.value(); if (value null) return; if (minVal null || value minVal) { minState.update(value); } else if (midVal null || value midVal) { midState.update(value); } else { out.collect(true); } } }这里最容易被忽略的是状态清理。流处理任务跑几天甚至几个月状态数据如果不清理最终会撑爆 RocksDB 或内存。给状态配置 TTL 是基本操作。还要注意状态恢复和容错问题如果下游需要精确一次语义这个算子要有对应的 checkpoint 配置。4.3 状态管理与复杂度权衡从算法到实时工程化一个核心变化是“数组”被换成了“流”。数组的长度是已知的流没有长度数组可以随机访问流只能逐个处理数组的内存占用固定流的状态需要自己控制生命周期。flink 里做这类检测时还有一种更轻的方案不管理状态而是在窗口内做局部判断。比如每一分钟的 tumbling window把窗口内数据收集成列表再调用离线版函数。优点是实现简单、容易复用离线代码缺点是窗口边界上的跨窗口三元组检测不到且窗口内数据量如果很大内存压力会成倍增加。所以选择哪种方案本质上是实时性、状态开销和语义完整性的三方权衡。如果业务能接受“跨窗口不检测”局部窗口方案省事如果必须精确检测就得用带状态的算子。这也是工程化过程中反复出现的主题没有最好的方案只有最合适的取舍。5. 常见问题与排查实录5.1 边界条件重复元素、负数、单元素数组为什么等号那么重要我在实际带新人时发现最容易写错的地方就是判断条件里的等号。贪心逻辑里如果写成而不是在遇到重复数字时会把 first 和 second 维持成同一个值最终错误地返回 true 或漏判。举个例子数组是 [1, 2, 2]正确结果应该是 false因为不存在严格递增的三元组三元组长度都不够。但如果在 second 更新时用了第二次遇到 2 时由于 2 first1且 2 second之前 second 是无穷大会把 second 更新为 2。等到后续再出现大于 2 的数比如 [1, 2, 2, 3]就会错误地认为存在三元组返回 true。从语义上看2 和 2 是相等的不能构成严格递增。反之使用 才能保证 first 和 second 严格递增。这类问题在刷题评测里很容易暴雷因为评测数据会包含大量边界用例。负数与最小值初始化另一个常见坑是初始化。如果把 first 初始化为 0 或者数组首个元素当输入全是负数时可能出现判断异常。比如输入 [-1, -2, -3]正确的返回值应该是 false但如果 first 初始化为 0遍历到 -1 时因为 -1 0所以 first -1遍历到 -2 时-2 -1first -2遍历到 -3 时-3 -2first -3。最终 first 一直在更新second 还是初始值未触发 true结果也算对但这种写法非常脆弱。如果 first 初始化为 0second 初始化为 0遇到 [-1, -2, 1, 2] 这样的用例会因为 first-2、second1、21 而返回 true实际上不存在三元组吗不对-2、1、2 是存在的所以结果正确。但如果遇到全部都是负数的倒序数组则可能因为 second 初始为 0导致后面的任何一个负数都小于等于 second一直不会触发。所以最稳妥的初始化方式是使用正无穷float(inf) 或 Integer.MAX_VALUE而不是用数组首个元素或 0。5.2 数据规模与表达式溢出如果把代码从 Python 迁移到 C 或 Java要格外注意整型溢出。典型的错误是把 first 初始化为一个很大的数比如 1e9然后输入里又有更大的数判断就会失败。更稳妥的做法是使用 INT_MAX 或 Integer.MAX_VALUE在语言层面就保证了“无穷大”不会小于任何可能输入。还有一个问题是如果数组长度达到 10^9 量级Python 的逐元素循环速度会显得很慢。工程化时可以考虑用 numpy 做向量化优化把循环改写为批量比较。不过这会牺牲可读性一般只在非常极端的性能场景下才值得做。5.3 从“能跑”到“能维护”的坑工程化落地时我踩过几类跟算法本身无关的坑没有处理空指针或 null 输入导致线上调用直接 NPE。把判断逻辑和业务动作耦合在一起导致后续想复用判断函数时不得不拆分。缺少日志和可观测性当算法返回 true 时不知道是基于哪些具体数据点判断出来的排查困难。针对最后一点比较好的做法是在返回 true 的同时记录当前 minVal、midVal 和触发值。这样当业务告警出现时可以快速确认算法逻辑是否符合预期而不是对着一个布尔值干瞪眼。5.4 排查技巧与自检清单我在做代码评审时会给自己一份固定排查清单是否有等号错误严格递增场景下等号很可能决定胜败。是否处理了长度小于 3 的输入初始化值是否足够大足以覆盖负数输入重复元素测试是否通过如果改成通用的 K 元检测测试是否覆盖 K1、K2、Kn 等异常场景如果这些问题都过了一遍这个算法落地基本就是稳的。6. 实际落地中的体会与扩展思路这道递增三元子序列题表面上是个算法小题但从解法演进到工程化的过程我体会最深的一点是最优解往往不是最复杂的解而是信息冗余最少的解。双变量贪心把“左侧最小值”和“次小值”这两个最关键的状态压缩下来只保留真正影响判断的信息。在工程化中这种“找到必要状态然后只维护必要状态”的思维方式比背下某个特定解法更有用。比如在 flink 流计算场景里你不可能保留所有历史元素只能找到那两三个关键状态让它们在数据流中持续更新。这种思维和算法题本身是相通的。最后分享一个小技巧如果你在面试或工程讨论中遇到这道题不要急着甩出双变量代码。先把从暴力到前缀最优值的演进过程说出来再落到双变量。这个思考过程比代码本身更能体现算法素养。而在工程落地时再进一步把命名、封装、测试和流式适配补齐一道小题也能变成一篇完整的技术方案。我后来在做趋势检测和阈值告警模块时多次用到了类似的状态压缩思路效果都很稳定。