正文索引 [隐藏]

传送门

拿到这题第一思路肯定是n³直接暴，但肯定会超时，事实上定一动二的n²都能超，那么根据传统优化思路，只枚举一个就行。

根据枚举位置的不同，有两种不一样的思路。

方法一：有序集合(枚举k)

思路

枚举j，即寻找一个满足“i<j<k且nums[i]<nums[k]<nums[j]”的j。因为最左侧的i同时满足下标最小与值最小，所以可以用一个变量来记录当前最小值，也就省去了枚举i的开销。

在这同时，用一个有序集合来维护自当前枚举的位置到nums尾部的序列，它的作用是从其中找k。

在枚举时，没枚举到一个j，就从该有序集合中找到“第一个大于nums[i](也就是上文提到过的’当前最小值’)的值”，根据贪心思想，它就最可能是满足条件的k。如果此时的nums[j]大于该值，则可以直接返回true；否则维护nums[i]的最小性，维护该有序集合的长度，再进行下一轮枚举，直到尾部。

代码

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        // 左区间最小值
        int left = nums[0];
        // 右区间序列
        multiset<int> right;
        const int n = nums.size();

        if (n < 3) {
            return false;
        }

        // 右维护
        for (int k = 2; k < n; k++) {
            right.insert(nums[k]);
        }

        for (int j = 1; j < n - 1; j++) {
            // 左边值已经小于nums[j]
            // 判断右边
            if (left < nums[j]) {
                auto it = right.upper_bound(left);
                if (it != right.end() && (*it) < nums[j]) {
                    return true;
                }
            }

            left = min(left, nums[j]);
            // 维护集合为"从当前到队尾"
            right.erase(right.find(nums[j+1]));
        }

        return false;
    }
};

方法二：单调栈(枚举i)

思路

如果我们要枚举i，即确定存在一个数对(j,k)满足i<j<k且nums[j]>nums[k]，只需要维护一个从尾到头的单调递减栈，并记录它弹出过的最大值即可。

不难想通，设这个最大值为kmax，如果kmax大于nums[i]，即说明i往后若干的下标的位置处存在一个比它大的kmax，而且这些位置之间的值一定小于等于kmax。那么我们令j=kmax，就可以找到符合题设的组合。

代码

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        stack<int> stk;
        int n = nums.size(), k = INT_MIN;

        for(int i = n - 1; i >= 0; i--){
            if(nums[i] < k) {
                return true;
            }

            while(!stk.empty() && stk.top() < nums[i]) { 
                k = max(k, stk.top()); 
                stk.pop();
            }
            stk.push(nums[i]);
        }

        return false;
    }
};

参考自：https://leetcode-cn.com/problems/132-pattern/solution/xiang-xin-ke-xue-xi-lie-xiang-jie-wei-he-95gt/