Window Maximum · 朴素引子

窗内取最值：为什么不能简单「出一进一」

在窗口和一页，窗口和能靠「一减一加」增量更新；换成最大值就失效了——滑走的那个若恰是当前最大，新最大值无法靠一次减法算出来，得在剩下 $k-1$ 个里重找。所以先看最直接（也最慢）的做法：窗口停在 $[L, L+k-1]$ ，就把这 k 个数从头比一遍取最大值，记下来；然后窗口右移一格，再从头比一遍。下面单步展示每一次比较——注意窗口右移时，中间那 $k-2$ 个数上一轮刚比过、这一轮又被重比了。

1 · 慢在「重复比较」

窗口从 $[L, L+k-1]$ 滑到 [L+1, L+k]，其实只出去一个 nums[L]、进来一个 nums[L+k]，中间 $k-2$ 个数原封不动——可暴力法不记忆上一轮的结论，每个窗口都把这 k 个数从头比一遍。总比较次数 $= (n-k+1)\cdot k$ ，当 k 接近 n/2 时退化到 $O(n^2)$ 。

避免重复比较的办法见双端单调队列：维护一组「仍可能成为最大值」的候选，窗口滑动时只做增量更新——每个数只进队、出队各一次，总计 $O(n)$ 。