NO IMAGE

題目

Given a sequence of n integers a1, a2, …, an, a 132pattern
is a subsequence ai, aj, ak such that i < j < kand 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.

n will be less than 20,000.

樣例

Given nums = [1, 2, 3, 4]
return False // There is no 132 pattern in the sequence.

Given nums = [3, 1, 4, 2]
return True // There is a 132 pattern in the sequence: [1, 4, 2].

題目來源:Link

LintCode連結:Link

分析

(1)方法一:利用最小值陣列

TC = O(n) O(n^2)

SC = O(n)

1)遍歷陣列,對於 i,找到 0~i 中的小於 nums[i] 的最小值,存在 mins[i] 中,mins[i] 可能等於 nums [i], 這表明其右邊沒有比他更小的數,不影響後面的判斷

2)從右往左遍歷陣列,維護一個list,裡面是按照插入排序排列的,找到小於當前元素的最大值 max,與 min[i] 比較,若 max > mins[i],則找到了一個132

(1)方法二:利用棧

TC = O(n)

SC最壞:O(n)

SC最好:O(1)

1)用 knum 標記 k 代表的值(132模式中的2),Stack 裡面存的是遍歷到當前位置所有大於 knum的值(相當於132模式中的3),遍歷的當前值(相當於132模式中的1),若nums[i] < knum 則表示發現了132

2)遍歷過程中,如果當前小於棧頂,則壓棧,如果大於棧頂,證明發現了比當前 knum 對應的 “3” 模式更大的數,則 pop 到 nums[i] < stack.peek(),pop的值賦值給knum,就是小於當前 nums[i] 右邊的最大值(棧中的元素自頂向下是遞減的)

3)有一種可能是 nums[i] 右邊小於他的最大值,之前就被彈出,但是不要緊,由於棧裡面放的是比當前 knum 大的數,且可定是連續遞增的,若遍歷中遇到了比棧頂更大的數,更新的 knum可定是比之前的更大,num[i] 都沒有機會找自己的 knum,因為既然他的右邊小於他的最大值都已經彈出,證明棧裡面的都比他大,他只能被放進棧裡面。

4)在132模式中,若2模式代表3模式的右邊小於3模式的最大,若1模式代表3模式的左邊小於3模式的最小,則1模式與2模式之間最大的3模式可定囊括其他3模式,而此方法就是向最大3模式逼近

程式碼

(1)方法一

public class Solution {
/**
* @param nums a list of n integers
* @return true if there is a 132 pattern or false
*/
public boolean find132pattern(int[] nums) {
if(nums==null) return false;
int n = nums.length;
if(n<3) return false;
int[] mins = new int[n];
mins[0] = nums[0];
for(int i=1; i<n; i  ){
mins[i] = Math.min(mins[i-1],nums[i]);
}
int max = nums[n-1];
Stack<Integer> s = new Stack<Integer>();
for(int i=n-1; i>-1; i--){
while(!s.isEmpty() && nums[i]<s.peek()){
s.pop();
}
if(s.isEmpty()){
s.add(nums[i]);
continue;
}else{
max = s.peek();
if(max>mins[i])
return true;
s.add(nums[i]);
}
}
return false;
}
}

(2)方法二

public class Solution {
/**
* @param nums a list of n integers
* @return true if there is a 132 pattern or false
*/
public boolean find132pattern(int[] nums) {
if(nums == null) return false;
int n = nums.length;
if(n<3) return false;
Stack<Integer> s = new Stack<Integer>();
int knum = Integer.MIN_VALUE;
for(int i=n-1; i>=0; i--){
if(nums[i]<knum) return true;
while(!s.isEmpty() && nums[i]>s.peek()){
knum = s.pop();
}
s.add(nums[i]);
}
return false;
}
}