Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

Follow up: The O(n^2) is trivial, could you come up with the O(n logn) or the O(n) solution?

Example 1:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: nums = [-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].

Constraints:

• n == nums.length
• 1 <= n <= 104
• -109 <= nums[i] <= 109

132模式。题意是给一个数组，请问数组里面是否存在一个子序列subsequence满足i < j < k同时nums[i] < nums[k] < nums[j]。

这道题不涉及算法，我这里提供两种做法，一种利用了treemap，一种利用了stack。

treemap的做法，首先我们遍历input数组，统计每个数字出现了几次，用treemap记录好。再一次遍历input数组，此时遇到一个数字，就从treemap中减去这个数字，直到把这个数字在treemap中的key移除为止。在第二次遍历的过程中，记录一个最小值min。如果在过程中发现有一个数字num比min大，同时在treemap中可以找到另一个数字既严格大于min（treemap.higherKey(min)），又小于当前的num，则说明找到了这个132模式。其中treemap的higherKey()函数是表示找一个严格大于当前数字的key，注意它和ceilingKey()的区别。

时间O(nlogn) - treemap找higherKey的时间复杂度

空间O(n)

Java实现

 1 class Solution {
 2     public boolean find132pattern(int[] nums) {
 3         TreeMap<Integer, Integer> treemap = new TreeMap<>();
 4         for (int num : nums) {
 5             treemap.put(num, treemap.getOrDefault(num, 0) + 1);
 6         }
 7         int min = Integer.MAX_VALUE;
 8         for (int num : nums) {
 9             int count = treemap.get(num);
10             if (count > 1) {
11                 treemap.put(num, count - 1);
12             } else {
13                 treemap.remove(num);
14             }
15             if (num <= min) {
16                 min = num;
17             } else {
18                 Integer target = treemap.higherKey(min);
19                 if (target != null && target < num) {
20                     return true;
21                 }
22             }
23         }
24         return false;
25     }
26 }

 

第二种方法是用stack，而且是从后往前遍历数组。遍历过程中，记录一个变量mid表示中间那个数字。因为这个数字需要出现在1和3之后，所以从后往前遍历是make sense的。一开始stack为空的时候就往stack放入nums[i]。当stack不为空的时候，判断当前数字nums[i]是否大于stack.peek()，若大于则stack.pop()并且把pop出来的元素赋给mid。此时pop出来的元素因为是比较靠后的，所以其实mid记录的是132模式里的那个2。我们试图找一个3之后最大的2，这样会留更多余地给1。所以再往前扫描的时候，一旦发现有nums[i] < mid则return true。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public boolean find132pattern(int[] nums) {
 3         Stack<Integer> stack = new Stack<>();
 4         int mid = Integer.MIN_VALUE;
 5         for (int i = nums.length - 1; i >= 0; i--) {
 6             if (nums[i] < mid) {
 7                 return true;
 8             } else {
 9                 while (!stack.isEmpty() && nums[i] > stack.peek()) {
10                     mid = stack.pop();
11                 }
12                 stack.push(nums[i]);
13             }
14         }
15         return false;
16     }
17 }

 

LeetCode 题目总结