【面试高频题】难度 4/5，单调栈的热门运用

标题描述

这是 LeetCode 上的 456. 132 形式 ，难度为 中等。

Tag : 「单调栈」

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

假设 nums 中存在 132 形式的子序列 ，回来 true；否则，回来 false。

进阶：很简略想到时刻复杂度为 O(n2)O(n^2)O(n2) 的解决方案，你能够规划一个时刻复杂度为 $O(n\log n)$ 或$O(n)$ 的解决方案吗？

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• $n=nums.length$
• 1<=n<=1041 <= n <= 10^41<=n<=104
• −109<=nums[i]<=109-10^9 <= nums[i] <= 10^9−109<=nums[i]<=109

基本思路

朴素的做法是分别对三个数进行枚举，这样的做法是 O(n3)O(n^3)O(n3) 的，数据规模是 10410^4104，稳稳超时。

事实上，这样的数据规模乃至不足以咱们枚举其间两个数，然后优化找第三个数的 O(n2)O(n^2)O(n2) 做法。

这时候依据数据规模会联想到树状数组，运用树状数组的复杂度是 $O(n\log n)$ 的，能够过。但是代码量会较多一点，还需求理解离散化等前置知识。题解也不太好写。

因而，咱们能够从 132 的大小特性去剖析，假设在确认一个数之后，如何快速找到另外两个数（咱们运用 ijk 来代指 132 结构）：

1. 枚举 i：因为 i 是 132 结构中最小的数，那么相当于咱们要从 i 后面，找到一个对数 (j,k)，使得 (j,k) 都满意比 i 大，一起 j 和 k 之间存在 j > k 的关系。因为咱们的遍历是单向的，因而咱们能够将问题转化为找 k，首先 k 需求比 i 大，一起在 [i, k] 之间存在比 k 大的数即可。

2. 枚举 j：因为 j 是 132 结构里最大的数，因而咱们需求在 j 的右边中比 j 小的「最大」的数，在 j 的左面找比 j 小的「最小」的数。这很简略联想到单调栈，但是朴素的单调栈是协助咱们找到左面或者右边「最近」的数，无法直接满意咱们「最大」和「最小」的要求，需求引入额定逻辑。

3. 枚举 k：因为 k 是 132 结构中的中心值，这里的剖析逻辑和「枚举 i」类似，因为遍历是单向的，咱们需求找到 k 左面的 i，一起保证 [i,k] 之间存在比 i 和 k 大的数字。

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

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

也许你还不理解是什么意思。不要紧，咱们一边证明一边说。

进程 & 证明

先说处理进程吧，咱们从后往前做，保护一个「单调递减」的栈，一起运用 k 记载一切出栈元素的最大值（k 代表满意 132 结构中的 2）。

那么当咱们遍历到 i，只需满意发现满意 nums[i] < k，阐明咱们找到了契合条件的 i j k。

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

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

这样做的实质是：咱们通过保护「单调递减」来保证现已找到了有用的 (j,k)。换句话说假设 k 有值的话，那么必定是因为有 j > k，导致的有值。也就是 132 结构中，咱们找到了 32，剩下的 i （也就是 132 结构中的 1）则是通过遍历进程中与 k 的比较来找到。这样做的复杂度是 $O(n)$ 的，比树状数组还要快。

从进程上剖析，是没有问题的。

搞清楚了处理进程，证明也变得非常简略。

咱们不失一般性的考虑任意数组 nums，假设实在存在 ijk 契合 132 的结构（这里的 ijk 特指一切满意 132 结构要求的组合中 k 最大的那个组合）。

因为咱们的比较逻辑只针对 i 和 k，而 i 是从后往前的处理的，必定会被遍历到；漏掉 ijk 的情况只能是：在遍历到 i 的时候，咱们没有将 k 更新到变量中：

1. 这时候变量的值要比实在情况下的 k 要小，阐明 k 还在栈中，而遍历位置现已到达了 i，阐明 j 和 k 一起在栈中，与「单调递减」的性质抵触。
2. 这时候变量的值要比实在情况下的 k 要大，阐明在 k 出栈之后，有比 k 更大的数值出栈了（一起必定有比变量更大的值在栈中），这时候要么与咱们假设 ijk 是 k 最大的组合抵触；要么与咱们遍历到的位置为 i 抵触。

综上，因为「单调递减」的性质，咱们至少能找到「遍历进程中」一切契合条件的 ijk 中 k 最大的那个组合。

Java 代码：

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() && d.peekLast() < nums[i]) {
                // 事实上，k 的变化也具有单调性，直接运用 k = pollLast() 也是能够的
                k = Math.max(k, d.pollLast()); 
            }
            d.addLast(nums[i]);
        }
        return false;
    }
}

Python3 代码：

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 stack[-1] < nums[i]:
                k = max(k,stack.pop())
            stack.append(nums[i])
        return False

C++ 代码：

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

• 时刻复杂度：$O(n)$
• 空间复杂度：$O(n)$

最后

这是咱们「刷穿 LeetCode」系列文章的第 No.456 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道标题，部分是有锁题，咱们将先把一切不带锁的标题刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简练的代码。假设触及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更抢手的「书面考试/面试」相关资料可访问排版精巧的 合集新基地