leetcode456-132模式

原题

给定一个整数序列:a1, a2, ..., an,一个132模式的子序列 ai, aj, ak 被定义为:当 i < j < k 时,ai < ak < aj。设计一个算法,当给定有 n 个数字的序列时,验证这个序列中是否含有132模式的子序列。

注意: n 的值小于15000。

示例1:

输入: [1, 2, 3, 4] 输出: False
解释: 序列中不存在132模式的子序列。

示例2:

输入: [3, 1, 4, 2] 输出: True
解释: 序列中有 1 个132模式的子序列: [1, 4, 2].

示例3:

输入: [-1, 3, 2, 0] 输出: True
解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].

解法

思想

  1. 暴力,从尾向头遍历,如果当前元素是132中的最后一个元素,则前面和中间一定分别有一个小于当前元素的元素和一个大于当前元素的元素。

  2. 栈,参考 https://leetcode-cn.com/problems/132-pattern/solution/132mo-shi-by-leetcode-2/

代码

  1. 暴力
class Solution {
    public boolean find132pattern(int[] nums) {
        for(int i = nums.length-1;i>=2;i--){
            int tail = nums[i];
            boolean hasPeek = false;
            for(int j = i-1;j>=0;j--){
                if(nums[j]>tail) hasPeek = true;
                else if(hasPeek&&nums[j]<tail) return true;
            }
        }
        return false;
    }
}
public class Solution {
    public boolean find132pattern(int[] nums) {
        if (nums.length < 3)
            return false;
        Stack<Integer> stack = new Stack<>();
        int[] min = new int[nums.length];
        min[0] = nums[0];
        for (int i = 1; i < nums.length; i++)
            min[i] = Math.min(min[i - 1], nums[i]);
        for (int j = nums.length - 1; j >= 0; j--) {
            if (nums[j] > min[j]) {
                while (!stack.isEmpty() && stack.peek() <= min[j])
                    stack.pop();
                if (!stack.isEmpty() && stack.peek() < nums[j])
                    return true;
                stack.push(nums[j]);
            }
        }
        return false;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode456-132%e6%a8%a1%e5%bc%8f/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月29日 16:25
下一篇 2020年1月30日 16:08

相关推荐

发表回复

登录后才能评论