题目描述

给定一个整数序列：$a_1, a_2, …, a_n$，一个132模式的子序列 $a_i, a_j, a_k$ 被定义为：当 $i < j < k$ 时，$a_i < a_k < a_j$。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。

注意：n 的值小于15000。

样例1

输入: [1, 2, 3, 4]

输出: False

解释: 序列中不存在132模式的子序列。

样例2

输入: [3, 1, 4, 2]

输出: True

解释: 序列中有 1 个132模式的子序列： [1, 4, 2].

样例3

输入: [-1, 3, 2, 0]

输出: True

解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].

算法

(单调栈) $O(n)$

我们可以从右往左遍历数组考虑每个数作为1或3的情况，同时维护一个次大值，这个次大值满足左边有一个数比它大，即是132模式中的2。假如我们遇到了小于当前次大值的数说明我们就找到了一个1，构成了一个132模式。否则我们就把当前数看成3，从当前数开始向右找到比当前数小的数并且更新次大值，这里我们只用向右找到第一个比当前数大的位置x即可，因为从该位置开始再往右的数如果小于当前数那么它也一定会小于这个比当前数大的数，也就是说他们之前已经在考虑x的时候被作为次大值更新过了，没有必要再重新更新一遍。

我们从右往左扫描数组并维护一个单调递减的栈，初始时次大值设为无穷小。如果当前数小于次大值说明我们找到了一个答案，否则考虑当前数作为3的情况，当当前数大于栈顶时说明我们找到了一个32模式，我们不断的弹出栈顶来更新2，即维护我们当前遇到的次大值，直到栈顶大于当前值为止。注意这时栈顶的右边可能还有之前被弹出过的小于当前数的值，但他们都会比当前的2小，即在扫描过程中这个2是会单调递增的，原因是如果不是单调递增的，那么这个第一次出现下降的数和当前的栈顶以及栈顶右边的数就构成了一个132模式，会在之前就直接返回。

时间复杂度

使用单调栈只需要扫描一遍数组，时间复杂度为 $O(n)$。

参考文献

这个问题与Knuth所提出来的 stack-sortable permutation 类似，即判断一个数组是否可以只用一个栈来进行排序，当且仅当它不包含231模式。而将本问题中的数组逆序，寻找132模式就变成了寻找231模式，也即判断数组是否可以仅用一个栈来进行排序。

C++ 代码

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        stack<int> stk;
        int two = INT_MIN;
        for (int i = nums.size() - 1; i >= 0; i -- ) {
            if (nums[i] < two) return true;
            while (stk.size() && nums[i] > stk.top()) {
                two = stk.top();
                stk.pop();
            }
            stk.push(nums[i]);
        }
        return false;
    }
};