# 132 Pattern

<https://leetcode.com/problems/132-pattern/description/>

> Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence a**i**, a**j**, a**k**such that**i**<**j**<**k**and a**i**< a**k**< a**j**. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.
>
> **Note:**&#x6E; will be less than 15,000.

## Thoughts

<https://leetcode.com/problems/132-pattern/discuss/>

我们假设存在从右到左第一个满足条件的s1在i处, i右边可能存在多种\<s3, s2>组合, 但我们只需找到最大的\<s2, s3>即可. 因此我们的任务是找到最大的s3的值. 我们可以维持一个栈, 每次遇到一个比栈顶大的数则把栈顶抛出作为s3, 新的栈顶则是s2. 对每次遍历遇到的数, 如果比s3小, 那我们就可以直接返回了 . 为什么这么做?

因为要求s3 < s2, 也就是说 **大的在左边, 小的在右边** , 而且由于我们是倒着遍历, 也就是说我们需要找到一对 **当前值大于之前遍历值** 的数对. 只有遇到单调增时才算找到合理的\<s2, s3>. 比如<5, 4>就是合理的倒着来单调增. 并且我们要找最大的pair, 比如<7, 6, 5, 4> 我们要找的是<7, 6>. 因此我们栈要维持单调减, 直到遇到不满足的情况(单调增)则意味着我们找到对合理的\<s2, s3>, 把栈顶抛出和当前元素组成一个合法的\<s2, s3>. 我们还要让新元素不断往上替换, 比如<0, 4, 1, 2, 3, 5> 我们要找的是<4, 3>, 栈内保留单调减的\[1, 2, 3, 5]. 现在4进来, 把1, 2, 3依次抛出, 3作为s3, 4作为s2.

## Code

```
class Solution {
    public boolean find132pattern(int[] nums) {
        int s3 = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] < s3) {
                return true;
            } else {
                while (!stack.isEmpty() && nums[i] > stack.peek()) {
                    s3 = stack.pop();
                }
                stack.push(nums[i]);
            }
        }
        return false;
    }
}
```

## Analysis

时空复杂度O(N).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/stack/wei-chi-di-zeng-huo-di-jian/132-pattern.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.