题目描述

给定一个整数序列 $a_1, a_2, …, a_n$，132 模式是 $a$ 的子序列 $a_i, a_j, a_k$，满足 $i < j < k$，并且 $a_i < a_k < a_j$。设计一个算法，读入 $n$ 个整数的数字序列，判断是否存在 132 模式。

样例

输入：[1, 2, 3, 4]
输出：False
解释：序列中没有132模式。

输入：[3, 1, 4, 2]
输出：True
解释：序列中的132模式为: [1, 4, 2]。

输入：[-1, 3, 2, 0]
输出：True
解释：序列中有三个132模式: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0]。

说明

• n 不超过 15000。

算法1

(离散化 + 树状数组) $O(n \log n)$

1. 首先将原数组元素离散化到区间 [1, n] 中，并将除了首元素外每个数字的值加入到树状数组的对应位置上，即对所有 $i>0$ 执行 update(a[i], 1)。
2. 定义 left_min 表示数组前 i 个元素的最小值，初始令 left_min=nums[0]。
3. 从位置 1 开始枚举 高峰 的位置，然后需要用树状数组寻找 i 之后是否有元素在 [left_min+1, nums[i]-1] 中。枚举时，首先将 nums[i] 从树状数组中删除，然后判断 num[i] 是否小于 left_min，若为真，则更新 left_min，继续枚举下一个位置；若为假，判断query(nums[i] - 1) - query(left_max) > 0，查看找到了 132 模式。

时间复杂度

• 离散化时间复杂度为 $O(n \log n)$，树状数组每次操作时间复杂度为 $O(\log n)$，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储离散化数组和树状数组。

C++ 代码

class Solution {
public:
    vector<int> f;
    int m;

    void update(int x, int y) {
        for (; x <= m; x += x & -x)
            f[x] += y;
    }

    int query(int x) {
        int tot = 0;
        for (; x; x -= x & -x)
            tot += f[x];
        return tot;
    }

    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        if (n < 3)
            return false;
        vector<int> b(nums);

        sort(b.begin(), b.end());
        m = unique(b.begin(), b.end()) - b.begin();
        b.resize(m);

        f = vector<int>(m + 1, 0);


        for (auto &x : nums)
            x = lower_bound(b.begin(), b.end(), x) - b.begin() + 1;

        for (int i = 1; i < n; i++)
            update(nums[i], 1);

        int left_min = nums[0];

        for (int i = 1; i < n; i++) {
            update(nums[i], -1);
            if (nums[i] < left_min)
                left_min = nums[i];
            else {
                if (query(nums[i] - 1) - query(left_min) > 0)
                    return true;
            }
        }

        return false;
    }
};

算法2

(单调栈) $O(n)$

1. 算法 1 中时间效率的瓶颈在查找 i 之后是否有数字位于 [left_min+1, nums[i]-1]。这一步可以利用单调栈来处理。首先我们可以发现，在从左往右遍历最高峰时，left_min 是单调递减的，所以 nums[i] 右边的数如果可以以 nums[i] 左边的数为高峰，构成 132 模式，则一定可以以 nums[i] 为高峰构成 132 模式。
2. 从数组末尾开始维护一个单调栈，如果发现 nums[i] 比栈顶元素严格大，则栈顶元素出栈，出栈时，记录下 right_min[i] 为栈顶元素。不断迭代出栈直到栈空或 nums[i] 不再比栈顶元素严格大。此时 right_min[i] 记录了右边第一个比它大的元素之前，比它小的最大的数（比较绕，大家可以仔细斟酌）。这里有一点需要注意一下，假设右边第一个比 nums[i] 大的数是 nums[k]，则 nums[k] 右边的数不需要考虑，因为我们会在枚举到 nums[k] 时考虑它们。
3. 从数组开头开始枚举 高峰 位置，同时维护 left_min 表示从数组开头到 高峰 位置中的最小元素，判断 left_min < right_min[i] && right_min[i] < nums[i] 成立则找到了 132 模式。

时间复杂度

• 维护单调栈是每个数字最多进栈一次，出栈一次，剩余部分都是在线性遍历数组，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储 right_min 和单调栈。

C++ 代码

class Solution {
public:  
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        if (n < 3)
            return false;

        vector<int> right_min(n, INT_MAX);
        stack<int> st;

        for (int i = n - 1; i >= 1; i--) {
            while (!st.empty() && nums[i] > nums[st.top()]) {
                right_min[i] = nums[st.top()];
                st.pop();
            }
            st.push(i);
        }

        int left_min = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] < left_min)
                left_min = nums[i];
            else {
                if (left_min < right_min[i] && right_min[i] < nums[i])
                    return true;
            }
        }

        return false;
    }
};