###### 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:

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++:

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;
    }
};