456. 132 Pattern

Question

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.

Solution

单调栈，专门用于找某一个元素的左边/右边第一个比自己大/小的位置。
递增单调栈会提出波峰，留下波谷。递减单调栈会剔除波谷，留下波峰。

我们需要找到同时满足j < k和nums[k] <[j]情况的位置。因此采用单调栈正合适。
我们枚举132模式中的“3”，由于我们要找到波谷，因此可以采用递增栈。

递增单调栈的实现：

当遍历的当前值小于栈顶元素时，不满足递增规律，因此挤出栈顶。
循环此操作直至当前栈顶于当前值满足递增规律或栈空。
此时的当前值是nums[j]，而最后一个被挤出的值就是nums[k]。
由于递增单调栈的性质，此时的nums[k] < nums[j]且nums[k]大于被挤出的所有元素。

对于nums[i]，我们可以通过遍历nums[]数组，计算出其在i位置的最小值，并存在放minOfLeft[]中。

Code

class Solution {
    public boolean find132pattern(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int[] minOfLeft = new int[nums.length];
        minOfLeft[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            minOfLeft[i] = Math.min(minOfLeft[i-1], nums[i]);
        }

        for(int j = nums.length-1; j >= 0; j--){
            int k = Integer.MIN_VALUE;
            while(!stack.isEmpty() && nums[j] > stack.peek()){
                k = stack.pop();
            }
            if(minOfLeft[j] < k){
                return true;
            }
            stack.push(nums[j]);
        }
        return false;
    }
}