为何同一问题下第二个代码循环语句更多却比第一个更快？

核心原因是两段代码的时间复杂度天差地别，第二段用了滑动窗口的优化思路，避免了大量重复计算。

第一段代码的低效根源 #

第一段的逻辑直白，但每一步都在做无用功：

• 循环遍历每个窗口的起始位置，每次截取长度为k的子数组arr[i:i+k]
• 对每个子数组调用max()，这一步要遍历k个元素才能得到结果

假设数组长度是n，窗口大小是k，那总共有n-k+1个窗口，每个窗口求max要花k次运算，总时间复杂度是O(n×k)。当n和k都比较大的时候（比如n是10万，k是1万），总运算量会达到10亿级别，肯定会超时。

第二段代码的优化逻辑 #

第二段代码巧妙利用了滑动窗口的特性，只在必要时重新计算最大值：

1. 先算出第一个窗口的最大值，存入结果列表
2. 滑动窗口时，分三种情况快速判断当前窗口的最大值：
   • 如果上一个窗口的最大值刚好是被移出窗口的元素（arr[i-k]），说明最大值被移走了，必须重新计算当前窗口的最大值
   • 如果上一个窗口的最大值比新加入的元素大，那最大值还在窗口里，直接复用即可
   • 如果新加入的元素比上一个最大值大，那它就是当前窗口的新最大值

这种逻辑下，绝大多数循环迭代只需要做1-2次比较和赋值，只有极少数情况需要重新遍历k个元素。平均下来，每个元素只被处理常数次，总时间复杂度是O(n)，比第一段的O(n×k)高效太多，所以即使循环里的语句更多，整体运行速度反而快很多。

内容的提问来源于stack exchange，提问作者Abhishek Kumar