题目描述：

LeetCode 456. 132 Pattern

Given a sequence of n integers a₁, a₂, ..., a_n, a 132 pattern is a subsequence a_i, a_j, a_k such that i < j < k and a_i < a_k < a_j. 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/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

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