从超时到AC；两种解法的深度剖析：力扣3904-北京尧图网络

一次看似正确的O(n)解法为何在LeetCode上惨遭TLE本文将带你拆解背后的时间复杂度陷阱。一、问题背景在刷力扣3904题时我遇到了一个有趣的现象两种思路几乎相同的解法一种超时一种顺利通过。这不仅仅是代码风格的区别而是对算法复杂度本质理解的体现。题目要求我们找到第一个稳定索引——即前缀最大值与后缀最小值之差不超过给定值k的最早位置。先看我的第一版代码注释部分和优化后的版本// 超时版本注释部分力扣3903行 int firstStableIndex(vectorint 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 i1; j n; j) { rightMin min(rightMin, nums[j]); } } } return -1; } // AC版本 //两次for循环是o(2n)但是常熟系数一般忽略于是还是o(n) int firstStableIndex(vectorint nums, int k) { int n nums.size(); vectorint 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 i1; j n; j) { rightMin min(rightMin, nums[j]); } }关键问题这个内部循环在最坏情况下会执行多少次考虑一个严格递减数组[5, 4, 3, 2, 1]i0rightMin1nums[0]5≠1不触发i1rightMin1nums[1]4≠1不触发i2rightMin1nums[2]3≠1不触发i3rightMin1nums[3]2≠1不触发i4rightMin1nums[4]1触发扫描后面0个元素这种情况其实还好因为rightMin一直没变。真正的噩梦是递增数组[1, 2, 3, 4, 5]i0rightMin1nums[0]1触发扫描i1到末尾4个元素找到新的rightMin2i1rightMin2nums[1]2触发扫描i1到末尾3个元素找到新的rightMin3i2rightMin3nums[2]3触发扫描i1到末尾2个元素i3rightMin4nums[3]4触发扫描i1到末尾1个元素i4rightMin5nums[4]5触发扫描0个元素总操作数43210 10次约等于n(n-1)/2。对于n100000这就是5×10⁹次操作——超时是必然的。AC版本真正的O(n)再看AC版本vectorint 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对于n100000就是20万次操作快了几个数量级。四、复杂度对比表维度超时版本AC版本时间复杂度O(n²) 最坏O(n)空间复杂度O(1)O(n)n10⁵时操作数≈5×10⁹≈2×10⁵LeetCode状态TLEAC五、为什么会写出超时版本这是一个很典型的认知偏差只看表面循环看到只有一个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)时间往往是值得的最坏情况分析不能仅凭平均情况或直觉判断复杂度优化思路对区间最值查询预处理是常用且高效的手段最后送给读者一句话写代码时不仅要看有几层循环更要看每条语句执行多少次。真正的复杂度藏在最坏情况的细节里。如果这篇文章对你有帮助欢迎点赞收藏也欢迎在评论区交流讨论.

从超时到AC；两种解法的深度剖析：力扣3904

相关推荐

WebScreen - 免费在线的桌面屏保合集

智慧政务服务中心解决方案：从架构设计到落地避坑指南

开学难受点，未来长一寸

更多资讯

宁波电工作业证书查询千万别踩坑：证书过期了不知道怎么复审延期

职业禁忌电工作业怎么考？保姆级教程帮你搞定特种作业证

办电工证要去哪里办电子证书查询

怀化溆浦县电工证报名全攻略工地太忙也能搞定官方报名入口

盐亭电工证怎么考证书过期了不知道怎么复审延期怎么报名

电工证怎样考取正规吗良心建议给你说清楚

今日更新

高压电工证哪里可以挂多久拿证全攻略：实操考试心里没底怕挂科别慌

电工证的理论题目在哪考，外省证怎么转过来

工地太忙根本没时间复习考试，职业学校的电工证值不值得考？

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？