这道题真的很有意思。
我第一遍做的时候很快写了个O(N^2)的solution。
后来想到可以做O(NLogN)的解。
在努力想O(N)的解的过程中卡住了, 有一步怎么都绕不过去。
后来看高票答案才理解。
参考文献如下。
https://leetcode.com/problems/132-pattern/discuss/94077/Java-O(n)-solution-using-stack-in-detail-explanation
O(N)的solution也是用栈来解决。这个我也知道。
从左往右扫描,栈里存过去的intervals, 用Deque<int[]> 表示, int[]是最小值和最大值。
如果栈为空或者当前的数n小于栈顶点的最小值,则把新的这个数放进一个(n, n)的数组里面丢进栈里去。
如果当前数n 等于栈顶点最小值或者是等于栈顶最大值,什么也不做。。
如果大于栈顶点最小值的话,分几种情况 。(难点在于这里!!)
1. 如果小于栈顶interval 最大值,返回true
2. 如果大于栈顶interval 最大值, 把栈顶的interval pop出来,更新一下最后这个interval
然后看一下刚pop出来的interval是不是能全cover现在栈顶的interval:
(a) 如果能,pop;
(b) 如果不能,则看一下具体为什么不能cover, 如果n是在栈顶的interval之间,则找到了132, 返回true; else 把最后那个interval塞回去,扫描下一个点。
除了顶上的元素,每个interval最多pop出来一次,所以时间是O(N)
class Solution {
public boolean find132pattern(int[] nums) {
int N = nums.length;
Deque<int[]> deque = new LinkedList<>();
for (int n : nums) {
if (deque.isEmpty() ||n < deque.peek()[0]) {
deque.push(new int[]{n, n});
} else if (n > deque.peek()[0]) {
if (n < deque.peek()[1]) return true;
// 难点在于这一段。
int[] itv = deque.pop();
itv[1] = n;
while (!deque.isEmpty()) {
if (n >= deque.peek()[1]) {
deque.pop(); // itv can fully cover this interval
} else {
if (n > deque.peek()[0]) return true; //found
break; // can't cover
}
}
deque.push(itv);
}
}
return false;
}
}
网友评论