456. 132 Pattern

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

        Stack<Integer> decreaseStack = new Stack<>(); // 从栈底至栈顶值非严格递减
        for (int j = nums.length - 1; j > 0; j--) { // 注意此处从右往左遍历
            int numK = Integer.MIN_VALUE;
            while (!decreaseStack.isEmpty() && nums[j] > decreaseStack.peek()) {
                // 弹出栈中小于 nums[j] 的元素，最后一个弹出的即为小于 nums[j] 的最大元素
                numK = decreaseStack.pop();
            }
            if (numK > leftMinArray[j]) {
                return true;
            }
            decreaseStack.push(nums[j]);
        }

        return false;
    }
}

References

456. 132 Pattern