一次看似正确的O(n)解法，为何在LeetCode上惨遭TLE？本文将带你拆解背后的时间复杂度陷阱。
一、问题背景
在刷力扣3904题时，我遇到了一个有趣的现象：两种思路几乎相同的解法，一种超时，一种顺利通过。这不仅仅是代码风格的区别，而是对算法复杂度本质理解的体现。
题目要求我们找到第一个"稳定索引"——即前缀最大值与后缀最小值之差不超过给定值k的最早位置。
先看我的第一版代码（注释部分）和优化后的版本：
// 超时版本（注释部分）力扣3903行 int firstStableIndex(vector<int>& nums, int k) { int n = nums.size(); if (n == 1) return 0; int rightMin = INT_MAX; for (int num : nums) rightMin = min(rightMin, num); int leftMax = INT_MIN; for (int i = 0; i < n; i++) { leftMax = max(leftMax, nums[i]); if (leftMax - rightMin <= k) return i; if (nums[i] == rightMin) { rightMin = INT_MAX; for (int j = i+1; j < n; j++) { rightMin = min(rightMin, nums[j]); } } } return -1; } // AC版本 //两次for循环是o(2n)但是常熟系数一般忽略，于是还是o(n) int firstStableIndex(vector<int>& nums, int k) { int n = nums.size(); vector<int> minValue(n); minValue[n - 1] = nums[n - 1]; for (int i = n - 2; i >= 0; --i) { minValue[i] = min(minValue[i + 1], nums[i]); } int maxValue = INT_MIN; for (int i = 0; i < n; ++i) { maxValue = max(maxValue, nums[i]); if (maxValue - minValue[i] <= k) { return i; } } return -1; }二、直观理解：两种解法在做什么？
场景比喻
想象你在一条街道上从左向右走，手里拿着一个记录牌（记录左边遇到的最大值），同时你需要知道右边街道上最小的房子高度。
第一种做法：一开始就记住整条街最矮的房子。每当你路过当前最矮的房子时，就重新跑回街道右侧，重新确认最矮的是谁。
第二种做法：出发前，就在每个位置贴好标签："从这里到终点，最矮的是XXX"。你只需要边走边看标签即可。
显然，第二种做法更聪明——用空间换时间。
三、时间复杂度深度分析
超时版本：披着O(n)外衣的O(n²)
表面上看，超时版本只有一个for循环，似乎是O(n)。但陷阱藏在rightMin的更新逻辑中：
if (nums[i] == rightMin) { rightMin = INT_MAX; for (int j = i+1; j < n; j++) { rightMin = min(rightMin, nums[j]); } }关键问题：这个内部循环在最坏情况下会执行多少次？
考虑一个严格递减数组：[5, 4, 3, 2, 1]
i=0：rightMin=1，nums[0]=5≠1，不触发
i=1：rightMin=1，nums[1]=4≠1，不触发
i=2：rightMin=1，nums[2]=3≠1，不触发
i=3：rightMin=1，nums[3]=2≠1，不触发
i=4：rightMin=1，nums[4]=1，触发！扫描后面0个元素
这种情况其实还好，因为rightMin一直没变。
真正的噩梦是递增数组：[1, 2, 3, 4, 5]
i=0：rightMin=1，nums[0]=1，触发！扫描i+1到末尾（4个元素），找到新的rightMin=2
i=1：rightMin=2，nums[1]=2，触发！扫描i+1到末尾（3个元素），找到新的rightMin=3
i=2：rightMin=3，nums[2]=3，触发！扫描i+1到末尾（2个元素）
i=3：rightMin=4，nums[3]=4，触发！扫描i+1到末尾（1个元素）
i=4：rightMin=5，nums[4]=5，触发！扫描0个元素
总操作数：4+3+2+1+0 =10次，约等于n(n-1)/2。
对于n=100000，这就是5×10⁹次操作——超时是必然的。
AC版本：真正的O(n)
再看AC版本：
vector<int> minValue(n); minValue[n - 1] = nums[n - 1]; for (int i = n - 2; i >= 0; --i) { minValue[i] = min(minValue[i + 1], nums[i]); }一次预处理，每个位置的后缀最小值已经算好。后续遍历时：
int maxValue = INT_MIN; for (int i = 0; i < n; ++i) { maxValue = max(maxValue, nums[i]); if (maxValue - minValue[i] <= k) { return i; } }每个元素只访问常数次，总操作数2n，对于n=100000就是20万次操作，快了几个数量级。
四、复杂度对比表
| 维度 | 超时版本 | AC版本 |
|---|---|---|
| 时间复杂度 | O(n²) 最坏 | O(n) |
| 空间复杂度 | O(1) | O(n) |
| n=10⁵时操作数 | ≈5×10⁹ | ≈2×10⁵ |
| LeetCode状态 | TLE | AC |
五、为什么会写出超时版本？
这是一个很典型的认知偏差：
只看表面循环：看到只有一个
for，就想当然认为是O(n)忽略隐藏循环：内部重新扫描的代价被低估
平均情况误导：可能心想"大部分情况不会触发重新扫描"，但最坏情况是算法分析必须考虑的
六、如何避免这类错误？
1. 识别"动态更新"的成本
当你需要频繁查询"区间最值"且数据会变化时，警惕每次O(n)的重新计算。
2. 经典优化思路
预处理：如本题的后缀数组
线段树/树状数组：动态区间查询
单调栈/队列：维护滑动窗口极值
堆：动态维护最值
3. 复杂度分析要严谨
不要只数循环层数，要计算每条语句在最坏情况下的总执行次数。
七、延伸思考
如果题目要求动态修改数组，那么预处理的后缀数组就不适用了。这时可以考虑：
线段树：O(log n) 查询区间最小值，O(log n) 更新
分块：O(sqrt(n)) 查询，平衡时间和空间
但本题是静态数组，预处理后缀数组是最优解——时间O(n)，空间O(n)。
八、总结
| 要点 | 说明 |
|---|---|
| 时间复杂度陷阱 | 隐藏循环可能将O(n)变为O(n²) |
| 空间换时间 | 用O(n)空间换取O(n)时间，往往是值得的 |
| 最坏情况分析 | 不能仅凭平均情况或直觉判断复杂度 |
| 优化思路 | 对区间最值查询，预处理是常用且高效的手段 |
最后送给读者一句话：
写代码时，不仅要看"有几层循环"，更要看"每条语句执行多少次"。真正的复杂度，藏在最坏情况的细节里。
如果这篇文章对你有帮助，欢迎点赞收藏，也欢迎在评论区交流讨论.
