BiruLyu
6/9/2017 - 6:26 PM

## 456. 132 Pattern(TreeSet).java

``````public class Solution {
public boolean find132pattern(int[] nums) {
if (nums == null || nums.length < 3) return false;
Deque<Integer> stack = new ArrayDeque<Integer>();
int len = nums.length;
int maxSecond = Integer.MIN_VALUE;
for (int i = len - 1; i >= 0; i--) {
if(nums[i] < maxSecond) {
return true;
}
while(!stack.isEmpty() && nums[i] > stack.peek()) {
maxSecond = stack.pop();
}
stack.push(nums[i]);
}
return false;

}
}
/*
[1,2,3,4]
[3, 1, 4, 2]
[-1, 3, 2, 0]
[1,2,3,4,-1,3]
[1,-2,3,4,-1,3,-2]
*/``````
``````public boolean find132pattern(int[] nums) {
if(nums == null || nums.length <= 2){
return false;
}
int[] leftSmall = new int[nums.length];
leftSmall[0] = nums[0];
for(int i = 1; i < nums.length; i ++){
leftSmall[i] = Math.min(leftSmall[i-1], nums[i]);
}
int[] rightSec = new int[nums.length];
rightSec[nums.length - 1] = Integer.MIN_VALUE;
TreeSet<Integer> set = new TreeSet<Integer>();
for(int i = nums.length - 2; i >= 0; i --){
Integer lower = set.lower(nums[i]);
if(lower == null){
rightSec[i] = Integer.MIN_VALUE;
}else{
rightSec[i] = lower;
}