LeetCode[132] Pattern

go4it 发布于2019-08-16 10:26 / 1144人阅读

摘要：复杂度思路维护一个里面有最大值和最小值。如果当前值小于的最小值，那么就将原来的压进去栈，然后在用这个新的的值再进行更新。如果没有适合返回的值，就重新更新当前的。

Leetcode[132] Pattern

Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

Note: n will be less than 15,000.

Example 1:
Input: [1, 2, 3, 4]
Output: False
Explanation: There is no 132 pattern in the sequence.

Example 2:
Input: [3, 1, 4, 2]
Output: True
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Stack

复杂度
O(N),O(N)

思路
维护一个pair, 里面有最大值和最小值。如果当前值小于pair的最小值，那么就将原来的pair压进去栈，然后在用这个新的pair的值再进行更新。如果当前值大于pair的最大值，首先这个值和原来在stack里面的那些pair进行比较，如果这个值比stack里面的值的max要大，就需要pop掉这个pair。如果没有适合返回的值，就重新更新当前的pair。

代码

Class Pair {
    int min;
    int max;
    public Pair(int min, int max) {
        this.min = min;
        this.max = max;
    }
}

public boolean find123Pattern(int[] nums) {
    if(nums == null || nums.length < 3) return false;
    Pair cur = new Pair(nums[0], nums[0]);
    Stack stack = new Stack<>();
    for(int i = 1; i < nums.length; i ++) {
        if(nums[i] < cur.min) {
            stack.push(cur);
            cur = new Pair(nums[i], nums[i]);
        }
        else if(nums[i] > cur.max) {
            while(!stack.isEmpty() && stack.peek().max <= nums[i]) {
                stack.pop();
            }
            if(!stack.isEmpty() && stack.peek.max > nums[i]) {
                return true;
            }
            cur.max = nums[i];
        }
        else if(nums[i] > cur.min && nums[i] < cur.max) {
            return true;
        }
    }
    return false;
}

云服务器 GPU云服务器 132邮箱 Pattern LeetCode V132

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69793.html

132pattern

摘要：记录即之前，里的最小值，即题目里的即所有不满足的直接跳过。已知那么找一个比大，又尽可能小的数找满足就最可能。找到后，比较是否满足满足就返回更新栈顶元素，表示表示 Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k an...

Raaabbit 2019-08-14 17:19 评论0 收藏0
leetcode132. Palindrome Partitioning II

摘要：题目要求现在有一个字符串，将分割为多个子字符串从而保证每个子字符串都是回数。我们只需要找到所有可以构成回数的并且得出最小值即可。即将字符作为，将字符所在的下标列表作为。再采用上面所说的方法，利用中间结果得出最小分割次数。题目要求 Given a string s, partition s such that every substring of the partition is a ...

jeyhan 2019-08-15 14:27 评论0 收藏0
[leetcode]132. Palindrome Partitioning II

摘要：用表示当前位置最少需要切几次使每个部分都是回文。表示到这部分是回文。如果是回文，则不需重复该部分的搜索。使用的好处就是可以的时间，也就是判断头尾就可以确定回文。不需要依次检查中间部分。 Given a string s, partition s such that every substring of the partition is a palindrome. Return the...

Airy 2019-08-14 16:54 评论0 收藏0
【实践】玩转正则表达式+JS正则处理函数

摘要：前言写这篇文章不是空穴来风，最近一个礼拜写了一个简单的脚本，用来处理上千个文件，以便于在某些特定字符的周围添加标记，先说一下我这个脚本使用场景主要是来识别中文具体做什么，之后会单独写一篇文章，此处只提该脚本作用，同时为不同的文件类型，包括，前言写这篇文章不是空穴来风，最近一个礼拜写了一个简单的nodejs脚本，用来处理上千个文件，以便于在某些特定字符的周围添加标记，先说一下我这个脚...

DoINsiSt 2019-08-21 17:47 评论0 收藏0
[Leetcode] Permutation Sequence 全排列序列

摘要：找规律复杂度时间空间思路由于我们只要得到第个全排列，而不是所有全排列，我们不一定要将所有可能都搜索一遍。根据全排列顺序的性质，我们可以总结出一个规律假设全排列有个数组成，则第个全排列的第一位是。然后将得到，这个就是下一轮的。 Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutati...

testHs 2019-08-14 12:34 评论0 收藏0