题目

给定一个整数序列：a1, a2, …, an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。

注意：n 的值小于15000。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/132-pattern
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

132 Pattern 132模式;
思路是我们维护一个栈和一个变量 third，
其中 third 就是第三个数字，也是 pattern 132 中的2，初始化为整型最小值，
栈里面按顺序放所有大于 third 的数字，也是 pattern 132 中的3，
那么我们在遍历的时候，如果当前数字小于 third，即 pattern 132 中的1找到了，我们直接返回 true 即可，因为已经找到了
注意我们应该从后往前遍历数组。
如果当前数字大于栈顶元素，那么我们将栈顶数字取出，赋值给 third，然后将该数字压入栈，
进一步来说，栈里存放的都是可以维持坐标 second > third 的 second 值，其中的任何一个值都是大于当前的 third 值，如果有更大的值进来，那就等于形成了一个更优的 second > third 的这样一个组合，并且这时弹出的 third 值比以前的 third 值更大，为什么要保证 third 值更大，因为这样才可以更容易的满足当前的值 first 比 third 值小这个条件，
举个例子来说吧，比如 [2, 4, 2, 3, 5]，由于是从后往前遍历，所以后三个数都不会进入 while 循环，那么栈中的数字为 5, 3, 2（其中2为栈顶元素），此时 third 还是整型最小，那么当遍历到4的时候，终于4大于栈顶元素2了，那么 third 赋值为2，且2出栈。此时继续 while 循环，因为4还是大于新栈顶元素3，此时 third 赋值为3，且3出栈。现在栈顶元素是5，那么 while 循环结束，将4压入栈。下一个数字2，小于 third，则找到符合要求的序列 [2, 4, 3]

代码

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

总结

单调栈，单调队列是为了及时淘汰次优的解，这个题目首先是逆序遍历的
这是一个启发的点，其次是third 的设置。