Leetcode 456. 132 Pattern

[Woodyiiiiiii]

这道题首先根据数据量知道不能用O(n^2)级别以上时间复杂度的算法；然后想着如何实现O(nlgn)甚至O(n)级别的算法，试想三个元素太多了，要想全部囊括肯定做不到的，我们试着站住1、3、2之中的某个元素，然后找到它与其余两者的关系。

从简单的入手，从3开始，定位1我们只要找到它的左边最小的元素就行了，定义一个变量在每次遍历时去存储最小值即可；接着定位2，这个稍微困难些，我们不能用定位1的方法去定位它，于是这里有两种方法。

第一种就是用TreeMap，key是数组的元素，value是其对应的出现次数，遍历时会减少，因为TreeMap是红黑树结构的，并且有对应方法ceilingKey()，返回参数是大于等于入参的key的最小值，这样一来我们可以用O(n)复杂度找到3的右边的2，从而判断是否存在132。解法如下：

解法一：

class Solution {
    public boolean find132pattern(int[] nums) {
        
        int n = nums.length;
        int leftMin = Integer.MAX_VALUE;

        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        for (int num : nums) {
            treeMap.put(num, treeMap.getOrDefault(num, 0) + 1);
        }

        for (int i = 0; i < n; i++) {

            if (i == 0 || i == n - 1) {
                treeMap.put(nums[i], treeMap.get(nums[i]) - 1);
                if (treeMap.get(nums[i]) == 0) {
                    treeMap.remove(nums[i]);
                }
                leftMin = Math.min(leftMin, nums[i]);
                continue;
            }

            Integer rightBigger = treeMap.ceilingKey(leftMin + 1);
            if (rightBigger != null && rightBigger < nums[i]) {
                return true;
            }

            treeMap.put(nums[i], treeMap.get(nums[i]) - 1);
            if (treeMap.get(nums[i]) == 0) {
                treeMap.remove(nums[i]);
            }
            leftMin = Math.min(leftMin, nums[i]);

        }

        return false;
        
    }
}

第二种就是单调栈的解法了，单调栈保证了栈底到栈顶的元素依次减少，对于一个元素，我们跟单调栈的元素对比，可以找到单调栈中小于它的并且最接近它的值，也就是3，这样保证选1的空间更大。

从右往左遍历数组，维护一个单调栈，里面的元素是3的候补，也就是可能成为3的元素，维护此变量放到下一次遍历时去做对比判断是否存在1；如果当前元素大于这个变量，说明满足单调栈的结构，可以push入栈；每次遍历时判断当前值能否成为1。

解法二：

class Solution {
    public boolean find132pattern(int[] nums) {
        
        int n = nums.length;
        int max3 = Integer.MIN_VALUE;
        // 单调栈，维护3的候选者
        Deque<Integer> stack = new LinkedList<>();

        for (int i = n - 1; i >= 0; --i) {
            if (nums[i] < max3) {
                return true;
            }
            while (!stack.isEmpty() && stack.peek() < nums[i]) {
                max3 = stack.pop();
            }
            if (nums[i] > max3) {
                stack.push(nums[i]);
            }
        }

        return false;
        
    }
}

---

参考资料：

• https://leetcode-cn.com/problems/132-pattern/solution/132mo-shi-by-leetcode-solution-ye89/