LeetCode 456. 132 Pattern

Problem

LeetCode 456. 132 Pattern

1. 题目简述

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.

Example 1:
Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Example2:
Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

2. 算法思路

这道题属于单调栈的高阶玩法。注意，单调栈的模板归模板，实际应用会大于“下一个更大/更小元素”。会有变种，这道题就是一个例子。

首先，我们需要遍历所有数字，假设所有数字都是”3”，然后找到它左侧的最小值，然后找到它右侧比它小的最大值。但是“找到右侧比它小的最大值”这个问题不能用单调栈模板直接解，我们需要将其做一个转化。假设有a[i]，a[i]右侧有一个数a[j]，a[j]是第一个大于a[i]的数，那么我们需要找的就是[i+1, j-1]之间小于a[i]的最大值。为什么？因为我们知道，a[i]左侧的最小值a1一定是<=a[j]左侧的最小值的，且a[i] < a[j]，如果a[j]的右侧有一个数字a[k]，使得a1,a[i]，a[k]满足“132”条件，那么a1，a[j]，a[k]也一定满足“132”条件，所以当我们遍历到a[j]的时候就会包含这种情况。所以我们只需要考虑a[i]与a[j]之间的比a[i]小的数字。

根据以上分析，我们知道a[j]就是a[i]的“下一个更大的数字”。因此可以转化为单调栈问题。那么问题来了，我们是要从左到右遍历，还是从右到左遍历呢？记得next greater element是从左到右，这题也是么？不是的，如果我们从左到右遍历，我们怎么知道它右侧数字的情况呢？因此我们需要从右向左遍历。

代码如下：

class Solution {
    public boolean find132pattern(int[] nums) {
        if (nums.length < 3) {
            return false;
        }
        
        // 找到每个数字右侧的比它小的最大数字（在右侧第一个比它大的数字之前）。如果没有的话则为Integer.MIN_VALUE。
        Stack<Integer> stack = new Stack<>();
        int[] right_min = new int[nums.length];
        Arrays.fill(right_min, Integer.MIN_VALUE);
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] > stack.peek()) {
                right_min[i] = stack.pop();
            }
            stack.push(nums[i]);
        }
        
        // 找到每个位置左侧的最小值
        int temp_min = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (temp_min != nums[i] && temp_min < right_min[i]) {
                return true;
            }
            temp_min = Math.min(temp_min, nums[i]);
        }
        
        return false;
    }
}