最短无序连续子数组

笨办法：把数组拷一份排好序，再从两头找第一个对不上的位置，中间就是答案。好写，但排序要 O(n log n) 时间、还多花一份 O(n) 空间。

正向走一遍：谁比它左边见过的最大值还小，谁就乱了，右边界就推到这。反向再走一遍：谁比它右边见过的最小值还大，谁也乱了，左边界就压到这。

正向扫描登场：max_seen 记左侧最大值：从左往右扫。手里攥着目前见过的最大值 max_seen，谁敢比它小，谁就破坏了升序。

i=0, x=2：刷新 max_seen=2：第一个数 2，没有左边，直接当最大值。一切正常。

i=1, x=6：刷新 max_seen=6：6 比 2 大，继续升序，最大值刷成 6。

i=2, x=4：4 ＜ 6，右边界推到 2：4 的左边出现过 6，比 4 大。说明 4 站错了位置，右边界先推到下标 2。

i=3, x=8：8 ≥ 6，刷新 max_seen=8：8 比之前的 6 大，没破坏升序，最大值刷成 8。右边界按兵不动。

i=4, x=10：10 ≥ 8，刷新 max_seen=10：10 又比 8 大，继续乖乖刷新最大值。它们都没破坏升序，右边界还停在 2。

i=5, x=9：9 ＜ 10，右边界推到 5：9 的左边见过 10，比 9 大。9 也站错了，右边界再往后推到下标 5。最后的 15 最大，不影响。正向扫完，右边界定格在 5。

反向扫描登场：i=6, x=15，min_seen=15：现在从右往左扫，攥着右边见过的最小值 min_seen。谁比它还大，谁就该被排序段收进去。最右的 15 没有右邻，直接当起始最小值，记成 15。

i=5, x=9：9 ≤ 15，刷新 min_seen=9：再往左到 9，它比 15 小，没破坏顺序，把最小值刷成 9。指针停在 9，面板也写 9，对齐。

i=4, x=10：10 ＞ 9，左边界压到 4：10 的右边有个更小的 9。10 排在 9 前面是错的，所以 10 也得进排序段，左边界压到下标 4。

i=2, x=4：刷新 min_seen=4：往左走到 8、4，它们都不比右边最小值大，没问题。4 比 9 还小，把最小值刷成 4。

i=1, x=6：6 ＞ 4，左边界压到 1：6 的右边有个更小的 4，6 排在前面是错的。左边界压到下标 1。再往左的 2 比 4 小，不动。反向扫完，左边界定格在 1。

灵魂帧慢放：两边夹出最短段：把两次扫描的结果叠在一起看：正向夹出右边界 5，反向夹出左边界 1。中间这段 [6,4,8,10,9] 就是最短无序段，长度 5-1+1 等于 5。

一句话本质：用两个方向的单调极值，从两头把最短无序段夹出来。

雷区实演：只找第一个下降会漏：如果只看“第一个下降位置”，会以为段在下标 2 就结束。但后面那串 2 仍然比左侧最大值 3 小，right 要一路推到下标 4。反向也把左边界压到 1。真实答案是排序 [3,2,2,2]，长度 4。

面试追问：把动画里的状态定义、边界处理和复杂度讲成自己的话，面试就稳了。

边界三连：有序、全逆序、带重复——三种极端先各跑一遍，心里就有底了。

把这题抽象成：正向维护一个单调极值、反向再维护一个，从两头夹出区间。接雨水、下一个排列都用得到这种双向扫描的思路。想巩固数组双向扫描，去 /leetcode-animation/ds?k=array 这个专题，或喊小欧帮你出几道同型题练手。