05 August 2008
a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j]，返回true如果有这么个subsequence
O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public boolean find132pattern(int[] nums) {
if(nums == null || nums.length < 3) {
return false;
}
for(int i = 0; i < nums.length - 2; i++) {
int bigger = nums[i];
for(int j = i + 1; j < nums.length; j++) {
// 1. We don't care about numbers
// less than a[i]
if(nums[j] <= nums[i]) continue;
// 2. If num is greater than bigger
// then update bigger
if(nums[j] >= bigger) {
bigger = nums[j];
} else {
// Now this number is greater than nums[i]
// see 1. and less than bigger, see 2.
return true;
}
}
}
return false;
}
stack - O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public boolean find132pattern (int[] nums) {
Stack <Integer> stack = new Stack ();
int second = Integer.MIN_VALUE;
for (int i = nums.length - 1; i >= 0; i--) {
if (nums [i] < second)
return true;
while (!stack.isEmpty() && nums [i] > stack.peek ())
second = stack.pop ();
stack.push (nums [i]);
}
return false;
}
}