乐趣区

关于后端:面试高频题难度-45单调栈的热门运用

题目形容

这是 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(n^2)$ 的解决方案,你能够设计一个工夫复杂度为 $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 <= 10^4$
  • $-10^9 <= nums[i] <= 10^9$

基本思路

奢侈的做法是别离对三个数进行枚举,这样的做法是 $O(n^3)$ 的,数据范畴是 $10^4$,稳稳超时。

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

这时候依据数据范畴会联想到树状数组,应用树状数组的复杂度是 $O(n\log{n})$ 的,能够过。然而代码量会较多一点,还须要了解离散化等前置常识。题解也不太好写。

因而,咱们能够从 132 的大小个性去剖析,如果在确定一个数之后,如何疾速找到另外两个数(咱们应用 ijk 来代指 132 构造):

  1. 枚举 i:因为 i 是 132 构造中最小的数,那么相当于咱们要从 i 前面,找到一个对数 (j,k),使得 (j,k) 都满足比 i 大,同时 jk 之间存在 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] 之间存在比 ik 大的数字。

以上三种分析方法都是可行的,但「枚举 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 的起源又是因为保护「枯燥递加」而弹出导致被更新的(满足 ik 之间,有比 k 要大的元素)。因而咱们找到了满足 132 构造的组合。

这样做的实质是:咱们通过保护「枯燥递加」来确保曾经找到了无效的 (j,k)。换句话说如果 k 有值的话,那么必然是因为有 j > k,导致的有值。也就是 132 构造中,咱们找到了 32,剩下的 i(也就是 132 构造中的 1)则是通过遍历过程中与 k 的比拟来找到。这样做的复杂度是 $O(n)$ 的,比树状数组还要快。

从过程上剖析,是没有问题的。

搞清楚了处理过程,证实也变得非常简略。

咱们不失一般性的思考任意数组 nums,如果实在存在 ijk 合乎 132 的构造(这里的 ijk 特指所有满足 132 构造要求的组合中 k 最大的那个组合)。

因为咱们的比拟逻辑只针对 ik,而 i 是从后往前的解决的,必然会被遍历到;漏掉 ijk 的状况只能是:在遍历到 i 的时候,咱们没有将 k 更新到变量中:

  1. 这时候变量的值要比真实情况下的 k 要小,阐明 k 还在栈中,而遍历地位曾经达到了 i,阐明 jk 同时在栈中,与「枯燥递加」的性质抵触。
  2. 这时候变量的值要比真实情况下的 k 要大,阐明在 k 出栈之后,有比 k 更大的数值出栈了(同时必然有比变量更大的值在栈中),这时候要么与咱们假如 ijkk 最大的组合抵触;要么与咱们遍历到的地位为 i 抵触。

综上,因为「枯燥递加」的性质,咱们至多能找到「遍历过程中」所有符合条件的 ijkk 最大的那个组合。

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 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。

在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。

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

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布

退出移动版