美文网首页
456. 132 Pattern

456. 132 Pattern

作者: 尚无花名 | 来源:发表于2019-03-19 01:57 被阅读0次

    这道题真的很有意思。
    我第一遍做的时候很快写了个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;
        }
    }
    

    相关文章

      网友评论

          本文标题:456. 132 Pattern

          本文链接:https://www.haomeiwen.com/subject/ddhwmqtx.html