标题描述
这是 LeetCode 上的 456. 132 形式 ,难度为 中等。
Tag : 「单调栈」
给你一个整数数组 nums
,数组中共有 n
个整数。132
形式的子序列 由三个整数 nums[i]
、nums[j]
和 nums[k]
组成,并一起满意:i<j<ki < j < k 和 nums[i]<nums[k]<nums[j]nums[i] < nums[k] < nums[j] 。
假设 nums
中存在 132
形式的子序列 ,回来 true
;否则,回来 false
。
进阶:很简略想到时刻复杂度为 O(n2)O(n^2) 的解决方案,你能够规划一个时刻复杂度为 O(nlogn)O(n \log{n}) 或O(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.lengthn = nums.length
- 1<=n<=1041 <= n <= 10^4
- −109<=nums[i]<=109-10^9 <= nums[i] <= 10^9
基本思路
朴素的做法是分别对三个数进行枚举,这样的做法是 O(n3)O(n^3) 的,数据规模是 10410^4,稳稳超时。
事实上,这样的数据规模乃至不足以咱们枚举其间两个数,然后优化找第三个数的 O(n2)O(n^2) 做法。
这时候依据数据规模会联想到树状数组,运用树状数组的复杂度是 O(nlogn)O(n\log{n}) 的,能够过。但是代码量会较多一点,还需求理解离散化等前置知识。题解也不太好写。
因而,咱们能够从 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
的比较即可。
也许你还不理解是什么意思。不要紧,咱们一边证明一边说。
进程 & 证明
先说处理进程吧,咱们从后往前做,保护一个「单调递减」的栈,一起运用 k
记载一切出栈元素的最大值(k
代表满意 132 结构中的 2)。
那么当咱们遍历到 i
,只需满意发现满意 nums[i] < k
,阐明咱们找到了契合条件的 i j k
。
举个,关于样例数据 [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 结构的组合。
这样做的实质是:咱们通过保护「单调递减」来保证现已找到了有用的 (j,k)
。换句话说假设 k
有值的话,那么必定是因为有 j > k
,导致的有值。也就是 132 结构中,咱们找到了 32,剩下的 i
(也就是 132 结构中的 1)则是通过遍历进程中与 k
的比较来找到。这样做的复杂度是 O(n)O(n) 的,比树状数组还要快。
从进程上剖析,是没有问题的。
搞清楚了处理进程,证明也变得非常简略。
咱们不失一般性的考虑任意数组 nums
,假设实在存在 ijk
契合 132 的结构(这里的 ijk
特指一切满意 132 结构要求的组合中 k
最大的那个组合)。
因为咱们的比较逻辑只针对 i
和 k
,而 i
是从后往前的处理的,必定会被遍历到;漏掉 ijk
的情况只能是:在遍历到 i
的时候,咱们没有将 k
更新到变量中:
- 这时候变量的值要比实在情况下的
k
要小,阐明k
还在栈中,而遍历位置现已到达了i
,阐明j
和k
一起在栈中,与「单调递减」的性质抵触。 - 这时候变量的值要比实在情况下的
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)
- 空间复杂度:O(n)O(n)
最后
这是咱们「刷穿 LeetCode」系列文章的第 No.456
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道标题,部分是有锁题,咱们将先把一切不带锁的标题刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简练的代码。假设触及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour… 。
在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更抢手的「书面考试/面试」相关资料可访问排版精巧的 合集新基地