132 Pattern

https://leetcode.com/problems/132-pattern/description/

Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, aksuch thati<j<kand ai< ak< aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

Note:n will be less than 15,000.

Thoughts

https://leetcode.com/problems/132-pattern/discuss/

我们假设存在从右到左第一个满足条件的s1在i处, i右边可能存在多种<s3, s2>组合, 但我们只需找到最大的<s2, s3>即可. 因此我们的任务是找到最大的s3的值. 我们可以维持一个栈, 每次遇到一个比栈顶大的数则把栈顶抛出作为s3, 新的栈顶则是s2. 对每次遍历遇到的数, 如果比s3小, 那我们就可以直接返回了 . 为什么这么做?

因为要求s3 < s2, 也就是说 大的在左边, 小的在右边 , 而且由于我们是倒着遍历, 也就是说我们需要找到一对 当前值大于之前遍历值 的数对. 只有遇到单调增时才算找到合理的<s2, s3>. 比如<5, 4>就是合理的倒着来单调增. 并且我们要找最大的pair, 比如<7, 6, 5, 4> 我们要找的是<7, 6>. 因此我们栈要维持单调减, 直到遇到不满足的情况(单调增)则意味着我们找到对合理的<s2, s3>, 把栈顶抛出和当前元素组成一个合法的<s2, s3>. 我们还要让新元素不断往上替换, 比如<0, 4, 1, 2, 3, 5> 我们要找的是<4, 3>, 栈内保留单调减的[1, 2, 3, 5]. 现在4进来, 把1, 2, 3依次抛出, 3作为s3, 4作为s2.

Code

class Solution {
    public boolean find132pattern(int[] nums) {
        int s3 = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] < s3) {
                return true;
            } else {
                while (!stack.isEmpty() && nums[i] > stack.peek()) {
                    s3 = stack.pop();
                }
                stack.push(nums[i]);
            }
        }
        return false;
    }
}

Analysis

时空复杂度O(N).