LeetCode 456. 132 Pattern

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2016/11/21/LeetCode-456-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].

题意解析

这道题的意思是，在一个数列里，是否存在有三个数A、B、C，它们的下标分别为i、j、k，其中i<j<k，A<C<B。

解法分析

维护一个有序的范围列表，列表的排序为由范围的起始从小到大排列。初始化时由第一个数作为范围的起始和结束放入队列。然后依次扫描剩下的数，在扫描的过程中有下面几种情况。

该数在某一范围内，返回true；
该数超出某一范围，更新这个范围；
该数大于目前所有值，则清空列表，并将当前最小和最大作为范围放入队列；
该数小于当前所有值，则将该值最为范围的起始和结束放入队列。

解题代码

public boolean find132pattern(int[] nums) {
	int min = Integer.MAX_VALUE;
	int max = Integer.MIN_VALUE;
	Map<Integer, Integer> ranges = new TreeMap<>();
	Set<Integer> keys = new TreeSet<>();
	for (int i = 0; i < nums.length; i++) {
		if (min > nums[i]) {
			min = nums[i];
		}
		if (max < nums[i]) {
			max = nums[i];
		}
		if (ranges.isEmpty()) {
			ranges.put(nums[i], nums[i]);
			keys.add(nums[i]);
		} else {
			for (int key : keys) {
				if (key < nums[i]) {
					if (nums[i] < ranges.get(key)) {
						return true;
					} else {
						ranges.put(key, nums[i]);
						if (max == nums[i]) {
							ranges.clear();
							keys.clear();
							ranges.put(key, nums[i]);
							keys.add(key);
							break;
						}
					}
				} else if (key > nums[i]) {
					ranges.put(nums[i], nums[i]);
					keys.add(nums[i]);
					break;
				}
			}
		}
	}
	return false;
}