LeetCode 456. 132模式 单调栈/medium

---

1.Description

给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。

如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

---

2.Example

输入：nums = [3,1,4,2]
输出：true
解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。

---

3.Solution

维护一个单调栈（从栈顶到栈底是单调递增或单调递减的，这里从栈顶到栈底是递增的），使k一直为次小值，当找到一个比次小值k还小的数时说明有了答案。

    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--) {
    
        	//当找到比次小值k小的数的时候，说明找到了i（k是次小的，栈里一定都是比k大的）
        	if(nums[i]<k) {
    
        		return true;
        	}
        	//栈里都是从i到数组尾中比k大的元素（且在栈中为递减顺序），当遇到比栈顶元素大时，维护k为次小值，将栈顶元素赋给k后在加入元素。
        	while(!stack.isEmpty()&&stack.peekLast()<nums[i]) {
    
        		k = stack.removeLast();
        	}
        	stack.addLast(nums[i]);
        }
        return false;
    }