2021-03-24 Leetcode-456

456.132模式

思路：维护一个单调栈.
方法：

• 从后向前遍历nums，维护一个递减栈和一个int值，该int值为仅次于当前元素 的第二大值，当遍历到前边的值比该int值小时则满足条件。
• 栈顶元素代表132中的3，在每次遍历进行第一行的比较时，numk代表132中的2，若新的num[i]<numk，则132出现。若新的num[i]比栈顶元素大，则while循环进行更新，原先的栈顶成为numk，更大的num[i]进栈。

/*执行用时：9 ms, 在所有 Java 提交中击败了43.28%的用户
内存消耗：38.9 MB, 在所有 Java 提交中击败了20.26%的用户*/
class Solution {
    public boolean find132pattern(int[] nums) {
        int len = nums.length;
        if(len < 3) return false;
        Stack<Integer> s = new Stack<>();
        int numk = Integer.MIN_VALUE;
        for(int i = len-1; i>=0; i--){
            if(nums[i] < numk)  return true;//出现1，3，2中的1
            while(!s.isEmpty() && s.peek() < nums[i]){
                numk = s.pop();
            }
            s.push(nums[i]);
        }
        return false;
    }
}