132 模式

别被名字唬住——它说的是「先一个最小的,再一个最大的,最后一个不大不小的中间值」,三者下标从左到右。

三层循环就是 O(n³),n 一大就跑不动。得想个一遍扫完的办法。

难点是「2」夹在中间。妙招是从右往左扫,边走边维护一个「目前见过的、能当 2 的最大值」——记作 k。

从右往左扫,只要当前数比栈顶大,就把栈顶弹出当「2」(更新 k=被弹的值)。之后若遇到比 k 还小的数,它就是「1」,132 凑齐!

盯住三样:cur 走到哪、栈里现在装着谁、k(候选的「2」)涨到多少。k 一旦 > 某个 cur,就中奖。

准备 · 从右往左：栈空着,k 先设成负无穷(还没有任何「2」候选)。我们从最右边的 2 开始,一路往左扫。

起点 · cur 指向最右：动画开始。cur 这个紫色指针停在最右的下标 3(值 2),左边三个先变灰表示还没扫到。我们一格一格往左走。

cur=3 · 看 nums[3]=2：cur 落在最右的 2。先问:2 比 k(此刻 -∞)小吗?不小。那它暂时没法当「1」,先看能不能进栈当「3 候选」。

cur=3 · 压入 2：栈是空的,直接把 2 压栈(变紫),让它当一个「3 候选」排队。继续往左。

cur=2 · 看 nums[2]=4：cur 移到 4。4 比 k(-∞)小吗?不小。再看栈顶是 2,4 比 2 大——这意味着 2 可以被「4 当 3、2 当 2」用上,把 2 弹出去当「2」。

cur=2 · 弹 2,更新 k：弹出 2,把 k 更新为 2(右边那个 2 变蓝,已当过「2」)。现在 k=2 的含义是:右边存在一个 2,它右边还有个比它大的数(就是当前的 4 会当 3)。

cur=2 · 压入 4：栈空了,把当前的 4 压栈当新的「3 候选」(紫格移到 4)。注意 k 已经是 2 了——只要接下来遇到比 2 小的数,132 就成立。

cur=1 · 先比 k：cur 移到下标 1(值 1)。每来一个新位置,第一步永远是先拿它和 k 比——因为 k 是合法的「2」,若当前值比 k 小,它就是「1」,132 当场成立。

cur=1 · 看 nums[1]=1：cur 移到 1。问:1 比 k(2)小吗?是! 这个 1 就是「1」,k=2 是「2」,栈里(或被弹时)的 4 是「3」——1 凑齐,直接 return true。

命中! · 132 = 1,4,2：三个角色对号入座:1(下标1),下标顺序 1→2→3 正好是「先小、再大、最后中」。这就是 132 模式。

这次会出现「一个 cur 连弹两次栈、把 k 抬高」的情形,正好补上单调栈的关键动作。

例2 · cur=3 看 0：从最右 0 开始。栈空,直接把 0 压进去当「3 候选」。

例2 · cur=2 比栈顶：cur 移到 2。先比 k:2 不小于 -∞。再比栈顶 0:2 比 0 大,该把 0 弹出去当「2」了。

例2 · cur=2 弹 0：弹出 0,k 更新为 0(右边那个 0 变蓝,已当过「2」)。

例2 · cur=2 压入 2：把当前 2 压栈。k 现在是 0:右边存在一个 0,且 0 右边有比它大的数。

例2 · cur=1 比栈顶：cur 移到 3。3 不小于 k(0)。再比栈顶 2:3 比 2 大,又能弹一个、把 k 抬得更高。

例2 · cur=1 弹 2,k 抬高：弹出 2,k 被抬到 2。看!k 越弹越大——我们总想要尽量大的「2」,这样更容易找到比它小的「1」。

例2 · cur=1 压入 3：把 3 压栈当「3 候选」。此刻 k=2:只要左边出现比 2 小的数,就中。

例2 · cur=0 看 -1：cur 到最左 -1。-1 命中! 这个例子展示了 k 靠连续弹栈被抬高,从而成全了答案。

例2 · 命中 -1,3,2：对号入座:-1(下标0)。负数也能当「1」——这正是 k 必须初始化成 -∞ 的原因,否则会漏掉负数开头的命中。

栈保证「3 候选」从底到顶递减;每次弹栈都是「找到了它右边的更大数」,被弹的就能当「2」。k 取所有被弹值的最大,最容易被左边的「1」击穿。

本题把「中间值 2」交给单调栈和 k 来盯,避免三重枚举。这种「固定一个、用栈维护另一个极值」的思路在区间/序列题里很常见。

雷区实演 · 从右扫为何对：从右扫的精髓:先把「2」和「3」的关系在右侧确认好(k=2 代表「右边有个 2,它右边还有更大的 3」),然后只等左边出现一个比 k 小的「1」。若从左扫,「2」还没出现就无从判断。

边界三连：递增、递减、含负数三种极端能讲对,代码就稳了——尤其负数那条印证 k 必须初始 -∞。

面试追问：把「为何从右扫」和「k 为何合法」讲透,是这题面试的得分点。