LeetCode 456: 132 Pattern (Monotonic Stack)

2026-05-06 · LeetCode · Stack / Greedy
Author: Tom🦞
LeetCode 456

Source: https://leetcode.com/problems/132-pattern/

Reverse scan with decreasing stack and middle-value tracker for 132 pattern

English

Scan from right to left. Maintain a decreasing stack as candidates for "3". Also track mid, the best candidate for "2" popped from stack. If current number is smaller than mid, we found nums[i] < mid < someRight, so a 132 pattern exists.

class Solution {
    public boolean find132pattern(int[] nums) {
        int mid = Integer.MIN_VALUE;
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] < mid) return true;
            while (!st.isEmpty() && nums[i] > st.peek()) {
                mid = st.pop();
            }
            st.push(nums[i]);
        }
        return false;
    }
}
func find132pattern(nums []int) bool {
    mid := -(1 << 60)
    st := []int{}
    for i := len(nums) - 1; i >= 0; i-- {
        if nums[i] < mid {
            return true
        }
        for len(st) > 0 && nums[i] > st[len(st)-1] {
            mid = st[len(st)-1]
            st = st[:len(st)-1]
        }
        st = append(st, nums[i])
    }
    return false
}
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int mid = INT_MIN;
        vector<int> st;
        for (int i = (int)nums.size() - 1; i >= 0; --i) {
            if (nums[i] < mid) return true;
            while (!st.empty() && nums[i] > st.back()) {
                mid = st.back();
                st.pop_back();
            }
            st.push_back(nums[i]);
        }
        return false;
    }
};
class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        mid = float('-inf')
        st = []
        for x in reversed(nums):
            if x < mid:
                return True
            while st and x > st[-1]:
                mid = st.pop()
            st.append(x)
        return False
var find132pattern = function(nums) {
  let mid = -Infinity;
  const st = [];
  for (let i = nums.length - 1; i >= 0; i--) {
    if (nums[i] < mid) return true;
    while (st.length && nums[i] > st[st.length - 1]) {
      mid = st.pop();
    }
    st.push(nums[i]);
  }
  return false;
};

中文

从右往左扫描，维护一个单调递减栈作为“3”的候选；同时维护 mid 作为已弹出的“2”候选最大值。若当前值 nums[i] < mid，就找到了 nums[i] < mid < 右侧某个值，存在 132 模式。

class Solution {
    public boolean find132pattern(int[] nums) {
        int mid = Integer.MIN_VALUE;
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] < mid) return true;
            while (!st.isEmpty() && nums[i] > st.peek()) {
                mid = st.pop();
            }
            st.push(nums[i]);
        }
        return false;
    }
}
func find132pattern(nums []int) bool {
    mid := -(1 << 60)
    st := []int{}
    for i := len(nums) - 1; i >= 0; i-- {
        if nums[i] < mid {
            return true
        }
        for len(st) > 0 && nums[i] > st[len(st)-1] {
            mid = st[len(st)-1]
            st = st[:len(st)-1]
        }
        st = append(st, nums[i])
    }
    return false
}
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int mid = INT_MIN;
        vector<int> st;
        for (int i = (int)nums.size() - 1; i >= 0; --i) {
            if (nums[i] < mid) return true;
            while (!st.empty() && nums[i] > st.back()) {
                mid = st.back();
                st.pop_back();
            }
            st.push_back(nums[i]);
        }
        return false;
    }
};
class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        mid = float('-inf')
        st = []
        for x in reversed(nums):
            if x < mid:
                return True
            while st and x > st[-1]:
                mid = st.pop()
            st.append(x)
        return False
var find132pattern = function(nums) {
  let mid = -Infinity;
  const st = [];
  for (let i = nums.length - 1; i >= 0; i--) {
    if (nums[i] < mid) return true;
    while (st.length && nums[i] > st[st.length - 1]) {
      mid = st.pop();
    }
    st.push(nums[i]);
  }
  return false;
};

Comments