## 题目描述：

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].
```

## 解题思路：

BST（Binary Search Tree 二叉查找树）

```首先利用TreeMap（采用红黑树实现）统计nums中所有元素的个数，记为tm

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

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

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

## 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;
}
}
``````

Pingbacks已关闭。

1. y119777 发布于 2016年11月13日 14:27 #

大神速度好快，求带[可怜],还有，这个题怎么换java了？

2. 在线疯狂 发布于 2016年11月14日 21:25 #

因为要用TreeMap，所以换成了Java :P