题目

力扣原题链接

给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。

如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

示例 1：

1
2
3

输入：nums = [1,2,3,4]
输出：false
解释：序列中不存在 132 模式的子序列。

示例 2：

1
2
3

输入：nums = [3,1,4,2]
输出：true
解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。

示例 3：

1
2
3

输入：nums = [-1,3,2,0]
输出：true
解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。

提示：

n == nums.length
1 <= n <= 2 * 10^5
-10^9 <= nums[i] <= 10^9

进阶：请使用时间复杂度为$O(n)$的方法。

解题思路

朴素的做法是分别对三个数进行枚举，这样的做法是 $O(n^3)$的，数据范围是$10^4$ ，稳稳超时。

事实上，这样的数据范围甚至不足以我们枚举其中两个数，然后优化找第三个数的$O(n^2)$做法。

这时候根据数据范围会联想到树状数组，使用树状数组的复杂度是$O(nlog_2n)$的，可以过。但是代码量会较多一点，还需要理解离散化等前置知识。

因此，我们可以从 132 的大小特性去分析，如果在确定一个数之后，如何快速找到另外两个数（我们使用 ijk 来代指 132 结构）：

枚举 i：由于 i 是 132 结构中最小的数，那么相当于我们要从 i 后面，找到一个对数 (j,k)，使得 (j,k) 都满足比 i 大，同时 j 和 k 之间存在 j > k 的关系。由于我们的遍历是单向的，因此我们可以将问题转化为找 k，首先 k 需要比 i 大，同时在 [i, k] 之间存在比 k 大的数即可。
枚举 j：由于 j 是 132 结构里最大的数，因此我们需要在 j 的右边中比 j 小的「最大」的数，在 j 的左边找比 j 小的「最小」的数。这很容易联想到单调栈，但是朴素的单调栈是帮助我们找到左边或者右边「最近」的数，无法直接满足我们「最大」和「最小」的要求，需要引入额外逻辑。
枚举 k：由于 k 是 132 结构中的中间值，这里的分析逻辑和「枚举 i」类似，因为遍历是单向的，我们需要找到 k 左边的 i，同时确保 [i,k] 之间存在比 i 和 k 大的数字。

以上三种分析方法都是可行的，但「枚举 i」的做法是最简单的。

因为如果存在 (j,k) 满足要求的话，我们只需要找到一个最大的满足条件的 k，通过与 i 的比较即可。

举例：

对于样例数据 [3, 1, 4, 2]，我们知道满足 132 结构的子序列是 [1, 4, 2]，其处理逻辑是（遍历从后往前）：

枚举到 2：栈内元素为 [2]，k = INF
枚举到 4：不满足「单调递减」，2 出栈更新 k，4 入栈。栈内元素为 [4]，k = 2
枚举到 1：满足 nums[i] < k，说明对于 i 而言，后面有一个比其大的元素（满足 i < k 的条件），同时这个 k 的来源又是因为维护「单调递减」而弹出导致被更新的（满足 i 和 k 之间，有比 k 要大的元素）。因此我们找到了满足 132 结构的组合。

代码

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

class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        Deque<Integer> d = new ArrayDeque<>();
        int k = Integer.MIN_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] < k) return true;
            while (!d.isEmpty() && nums[i] > d.peekLast()) {
                k = d.pollLast();
            }
            d.addLast(nums[i]);
        }
        return false;
    }
}

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        stack = []
        k = -(10 ** 9 + 7)
        for i in range(len(nums)-1, -1, -1):
            if nums[i] < k:
                return True
            while stack and nums[i] < stack[-1]:
                k = stack.pop()
            stack.append(nums[i])
        return False