---
# System prepended metadata

title: 456. 132 Pattern
tags: [Leetcode, stack, medium, python, array, c++]

---

###### tags: `Leetcode` `medium` `stack` `array` `python` `c++`

# 456. 132 Pattern

## [題目連結:] https://leetcode.com/problems/132-pattern/

## 題目:
Given an array of ```n``` integers ```nums```, a **132 pattern** is a subsequence of three integers ```nums[i]```, ```nums[j]``` and ```nums[k]``` such that ```i < j < k``` and ```nums[i] < nums[k] < nums[j]```.

Return ```true``` if there is a **132 pattern** in ```nums```, otherwise, return ```false```.

**Example 1:**
```
Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.
```
**Example 2:**
```
Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
```
**Example 3:**
```
Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].
```

## 解題想法:
* 找出數組中是否有三個位置(i<j<k)的數
    * nums[i]=first
    * nums[j]=second
    * nums[k]=third
    * **目標為first最小，second最大，third中**
* 使用stack:
    * 概念:
        * **先處理second與third關係**
        * **最後再判斷是否有合適的first<third**
    * stack作用:
        * 存的都是可以維持second>third的**second值**
        * pop出來則變成third
    * 流程:
        * 初始third為float('-inf')
        * **從尾開始遍歷數組**
        * first=當前遍歷的值
        * 每次判斷:
        *  if **first<third**:
            * return True
        * else: first>=third
            * 代表**當前的third需要被替換掉**
            * while stack and stack[-1]<first:
                * third=stack.pop()
            * 最後將first升格為second
                * stack.append(first)
                * **則依舊維持著stack中有至少一個元素(當前剛被存入的first)大於third**


## Python:
``` python=
class Solution(object):
    def find132pattern(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        #目標為 first:小 second:大 third:中
        #先處理second與third關係
        #最後在判斷是否有合適的first<third
        if len(nums)<3:
            return False
        third=float('-inf')
        stack=[] #存的都是可以維持second>third的second值
        #ex: 132
        #從尾開始找 
        for i in range(len(nums)-1,-1,-1):
            #loop3: 因為1<third:2  True
            first=nums[i]
            if first<third:
                return True
            else:
                #loop2: 2<first為3 代表2可以為third
                while stack and stack[-1]<first:
                    third=stack.pop()
                #loop1:先將2存入
                stack.append(first) #升格為second
        return False
    
result=Solution()
ans=result.find132pattern(nums = [3,1,4,2])
print(ans)
```

## C++:
``` cpp=
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int third=INT_MIN, n=nums.size(), first=0;
        stack<int> tmp;
        for (int i=n-1; i>=0; i--){
            first=nums[i];
            if (first<third)
                return true;
            else{
                while (!tmp.empty() && tmp.top()<first){
                    third=tmp.top(); tmp.pop();
                }
                tmp.push(first);
            }
        }
        return false;
    }
};
```