枚举

选对了枚举对象 就还是比较好理解的

最暴力的做法是 三层循环枚举三个数 判断是否满足关系 $O(n^3)$

优化$O(n^2)$ 先枚举132中的3
观察到“数1”只需取“数3”之前的最小值 而不需要每次都重复遍历判定
因此 对于每一个“数3” 只需遍历后续所有数 找到一个“数2”满足小于“数3”且大于“数1”

class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        if (n < 3) return false;  // 少于三个数 无解
        int minv = nums[0];  // 数3从第二个数开始枚举 所以最小值初始化为第一个数
        for (int i = 1; i < n - 1; i++) {
            if (minv >= nums[i]) {  // 不满足数1小于数3的关系 更新最小值 并枚举下一个数3
                minv = nums[i];
                continue;
            }
            for (int j = i + 1; j < n; j++) {  // 遍历数3后面的数 找到符合条件的数2
                if (nums[i] > nums[j] && minv < nums[j]) return true;
            }
        }
        return false;
    }
}

单调栈

思路是 使“数1”尽可能小，“数2”尽可能大（满足条件的前提下）

数1没问题 就是数3之前最小的数 因此也可以开一个数组事先遍历 记录下第i个位置前最小的数

优化的主要是数2的查找

之前暴力枚举时 找的是数3后面第一个大于数1且小于数3的值
（所以满足条件的数2可能有多个 但我们只需取其中一个）

为了使“数2”尽可能大 我们要找的就应该是小于数3的最大的数
（小于数3是必须的 为什么是找“最大” 数2越大 满足“数1<数2”的条件的概率就越大 ）
（换个说法 较小的数2若能满足“大于数1”的条件 那么较大数2也必然满足 但较大的满足了 小的却不一定）

所以需要一个算法来帮助我们 在给定数3的情况下 尽快的找到后面“小于数3的最大的数”
也就是单调栈
栈内存的是之前遍历过的数 越靠近栈底 数值越大

考虑从后往前遍历枚举数3 然后从单调栈中依次出栈找到最后一个小于当前数3的数值（即为“不大于数3的最大的数”） 判断这个出栈的数是否大于数1 是则构成132模式 否则把当前的数3入栈 枚举下一个数3
（当前数3不能满足132模式 说明数3比较小 导致最大的数2也不大于数1 因此继续遍历找更大的数3 当前的数3则作为一个小于“下一个数3”的数入栈 等待作为“下一个数2”参与比较）

出栈的过程可能会把小于“当前数3的下一个枚举目标”的最大的数丢弃了 但不影响最终结果
如果枚举目标可以和丢弃数构成132模式 那么存在两种情况
① 枚举目标大于当前数3 那么枚举目标完全可以与当前数3构成132 且当前数3必丢弃数大 构成的概率更高
② 枚举目标小于当前数3 那么数3应当也能与丢弃数构成132 也就不用枚举下一位了

如果对于某个枚举目标 存在栈顶元素一开始就大于该枚举值的情况 表明当前的数3必定不能找到一个符合条件的数2 直接入栈即可
但是为了与前面的操作保持类似 可以假设已事先取出一个栈顶元素为极小值 int temp = Integer.MIN_VALUE;

class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        if (n < 3) return false;

        int[] minv = new int[n];
        minv[0] = nums[0];
        for (int i = 1; i < n; i++) minv[i] = Math.min(minv[i-1], nums[i-1]);

        ArrayDeque<Integer> ad = new ArrayDeque<>();
        ad.push(Integer.MIN_VALUE);
        for (int i = n - 1; i > 0; i--) {
            int temp = Integer.MIN_VALUE;
            while (!ad.isEmpty() && ad.peek() < nums[i]) temp = ad.pop();
            if (temp > minv[i]) return true;
            ad.push(nums[i]);
        }

        return false;
    }
}