[LeetCode]132 Pattern

题目描述:

LeetCode 456. 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].

Example 3:

Input: [-1, 3, 2, 0]

Output: True

Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

题目大意:

给定整数序列a1, a2, ..., an,132模式是指一组序列 ai, aj, ak 满足  i < j < k and ai < ak < aj。设计算法判断长度为n的整数列表中是否包含132模式。

注意:n < 15000

解题思路:

BST(Binary Search Tree 二叉查找树)

首先利用TreeMap(采用红黑树实现)统计nums中所有元素的个数,记为tm

变量min记录访问过元素的最小值

遍历数组nums,记当前数字为num

  将num在tm中的计数-1,计数为0时将num从tm中删去

  如果num < min,则更新min值为num

  否则,若tm中大于min的最小元素<num,则返回true

遍历结束,返回false

Java代码:

public class Solution {
    public boolean find132pattern(int[] nums) {
        TreeMap<Integer, Integer> tm = new TreeMap<>();
        for (int num : nums) {
            tm.put(num, tm.getOrDefault(num, 0) + 1);
        }
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            int cnt = tm.get(num);
            if (cnt > 1) {
                tm.put(num, cnt - 1);
            } else {
                tm.remove(num);
            }
            if (num <= min) {
                min = num;
            } else {
                Integer target = tm.higherKey(min);
                if (target != null && target < num) {
                    return true;
                }
            }
        }
        return false;
    }
}

 

本文链接:http://bookshadow.com/weblog/2016/11/13/leetcode-132-pattern/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码