Leetcode 456.132 mode monotone stack /medium

---

1.Description

Give you an array of integers nums , There are... In the array n It's an integer .132 Subsequences of patterns By three integers nums[i]、nums[j] and nums[k] form , And meet ：i < j < k and nums[i] < nums[k] < nums[j] .

If nums in 132 Subsequences of patterns , return true ; otherwise , return false .

---

2.Example

 Input ：nums = [3,1,4,2]
 Output ：true
 explain ： There is... In the sequence  1  individual  132  Subsequences of patterns ： [1, 4, 2] .

---

3.Solution

Maintain a monotone stack （ From the top of the stack to the bottom of the stack is monotonically increasing or decreasing , Here, from the top of the stack to the bottom of the stack is increasing ）, send k Always the second lowest value , When a smaller value is found k A small number of hours shows that there is an answer .

    public boolean find132pattern(int[] nums) {
    
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int n = nums.length;
        if(n<3) {
    
        	return false;
        }
        int k = -1000000000;
        for(int i=n-1;i>=0;i--) {
    
        	// When the smaller value is found k When the number is small , It means that i（k It's a small , The stack must be full of comparisons k Big ）
        	if(nums[i]<k) {
    
        		return true;
        	}
        	// The stack is all from i To the end of the array k Big elements （ And it is in descending order in the stack ）, When you encounter an element larger than the top of the stack , maintain k Is the second smallest value , Assign the top element of the stack to k Then add elements .
        	while(!stack.isEmpty()&&stack.peekLast()<nums[i]) {
    
        		k = stack.removeLast();
        	}
        	stack.addLast(nums[i]);
        }
        return false;
    }