132 模式 图解题解

这道题到底在问什么

nums

[3, 1, 4, 2]

输出

true

命中

1 < 2 < 4(下标 1,3,2)

先想最直接的笨办法

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

最优解：一步一步想明白

1. 3别被名字唬住——它说的是「先一个最小的,再一个最大的,最后一个不大不小的中间值」,三者下标从左到右。
2. 4三层循环就是 O(n³),n 一大就跑不动。得想个一遍扫完的办法。
3. 5难点是「2」夹在中间。妙招是从右往左扫,边走边维护一个「目前见过的、能当 2 的最大值」——记作 k。
4. 6从右往左扫,只要当前数比栈顶大,就把栈顶弹出当「2」(更新 k=被弹的值)。之后若遇到比 k 还小的数,它就是「1」,132 凑齐!
5. 7盯住三样:cur 走到哪、栈里现在装着谁、k(候选的「2」)涨到多少。k 一旦 > 某个 cur,就中奖。
6. 8栈 [] · k = -∞栈空着,k 先设成负无穷(还没有任何「2」候选)。我们从最右边的 2 开始,一路往左扫。
7. 9cur=3 待处理动画开始。cur 这个紫色指针停在最右的下标 3(值 2),左边三个先变灰表示还没扫到。我们一格一格往左走。
8. 102 < k? 否(k=-∞)cur 落在最右的 2。先问:2 比 k(此刻 -∞)小吗?不小。那它暂时没法当「1」,先看能不能进栈当「3 候选」。
9. 11栈空 → 2 入栈栈是空的,直接把 2 压栈(变紫),让它当一个「3 候选」排队。继续往左。
10. 124 < k? 否 · 比栈顶 2 大cur 移到 4。4 比 k(-∞)小吗?不小。再看栈顶是 2,4 比 2 大——这意味着 2 可以被「4 当 3、2 当 2」用上,把 2 弹出去当「2」。
11. 13k ← 2 · 栈顶出栈弹出 2,把 k 更新为 2(右边那个 2 变蓝,已当过「2」)。现在 k=2 的含义是:右边存在一个 2,它右边还有个比它大的数(就是当前的 4 会当 3)。
12. 14栈空 → 4 入栈栈空了,把当前的 4 压栈当新的「3 候选」(紫格移到 4)。注意 k 已经是 2 了——只要接下来遇到比 2 小的数,132 就成立。
13. 151 vs k=2cur 移到下标 1(值 1)。每来一个新位置,第一步永远是先拿它和 k 比——因为 k 是合法的「2」,若当前值比 k 小,它就是「1」,132 当场成立。
14. 161 < k(2)? 是! → 命中cur 移到 1。问:1 比 k(2)小吗?是! 这个 1 就是「1」,k=2 是「2」,栈里(或被弹时)的 4 是「3」——1 < 2 < 4 凑齐,直接 return true。
15. 17下标 1<2<3 · 值 1<2<4三个角色对号入座:1(下标1)< 2(下标3)< 4(下标2),下标顺序 1→2→3 正好是「先小、再大、最后中」。这就是 132 模式。
16. 18这次会出现「一个 cur 连弹两次栈、把 k 抬高」的情形,正好补上单调栈的关键动作。
17. 190<k? 否 · 栈空压入从最右 0 开始。栈空,直接把 0 压进去当「3 候选」。
18. 202 vs 栈顶 0cur 移到 2。先比 k:2 不小于 -∞。再比栈顶 0:2 比 0 大,该把 0 弹出去当「2」了。
19. 212 > 栈顶 0 → 弹 0弹出 0,k 更新为 0(右边那个 0 变蓝,已当过「2」)。
20. 22栈空 → 2 入栈把当前 2 压栈。k 现在是 0:右边存在一个 0,且 0 右边有比它大的数。
21. 233 vs 栈顶 2cur 移到 3。3 不小于 k(0)。再比栈顶 2:3 比 2 大,又能弹一个、把 k 抬得更高。
22. 24弹 2 → k=2弹出 2,k 被抬到 2。看!k 越弹越大——我们总想要尽量大的「2」,这样更容易找到比它小的「1」。
23. 25栈空 → 3 入栈把 3 压栈当「3 候选」。此刻 k=2:只要左边出现比 2 小的数,就中。
24. 26-1 < k(2)? 是! → 命中cur 到最左 -1。-1 < k(2),命中! 这个例子展示了 k 靠连续弹栈被抬高,从而成全了答案。
25. 27下标 0<1<2 · 值 -1<2<3对号入座:-1(下标0)< 2(下标2)< 3(下标1)。负数也能当「1」——这正是 k 必须初始化成 -∞ 的原因,否则会漏掉负数开头的命中。
26. 28栈保证「3 候选」从底到顶递减;每次弹栈都是「找到了它右边的更大数」,被弹的就能当「2」。k 取所有被弹值的最大,最容易被左边的「1」击穿。
27. 29本题把「中间值 2」交给单调栈和 k 来盯,避免三重枚举。这种「固定一个、用栈维护另一个极值」的思路在区间/序列题里很常见。
28. 33[3,1,4,2] 先攒 k 再击穿从右扫的精髓:先把「2」和「3」的关系在右侧确认好(k=2 代表「右边有个 2,它右边还有更大的 3」),然后只等左边出现一个比 k 小的「1」。若从左扫,「2」还没出现就无从判断。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def find132pattern(self, nums):
        stack = []                 # 单调递减栈,存「3 候选」
        k = float('-inf')          # 「2」:已被弹出的最大次大值
        for i in range(len(nums) - 1, -1, -1):   # 从右往左
            if nums[i] < k:        # 找到「1」 → 132 成立
                return True
            while stack and stack[-1] < nums[i]:  # 比栈顶大就弹
                k = stack.pop()    # 被弹的当「2」,k 取最大
            stack.append(nums[i])
        return False

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        stack<int> st;                 // 存「3 候选」
        int k = INT_MIN;               // 「2」候选
        for (int i = nums.size() - 1; i >= 0; i--) {  // 从右往左
            if (nums[i] < k) return true;          // 找到「1」
            while (!st.empty() && st.top() < nums[i]) {  // 弹栈
                k = st.top(); st.pop();
            }
            st.push(nums[i]);
        }
        return false;
    }
};

class Solution {
    public boolean find132pattern(int[] nums) {
        Deque<Integer> stack = new ArrayDeque<>();  // 存「3 候选」
        int k = Integer.MIN_VALUE;     // 「2」候选
        for (int i = nums.length - 1; i >= 0; i--) {  // 从右往左
            if (nums[i] < k) return true;          // 找到「1」
            while (!stack.isEmpty() && stack.peek() < nums[i]) {  // 弹栈
                k = stack.pop();
            }
            stack.push(nums[i]);
        }
        return false;
    }
}

复杂度

面试官可能追问