|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
3 | | -importjava.util.Stack; |
4 | | -/**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. |
| 3 | +importjava.util.Deque; |
| 4 | +importjava.util.LinkedList; |
| 5 | +/** |
| 6 | + * 456. 132 Pattern |
| 7 | + * |
| 8 | + * Given a sequence of n integers a1, a2, ..., an, |
| 9 | + * a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. |
| 10 | + * Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list. |
5 | 11 |
|
6 | 12 | Note: n will be less than 15,000. |
7 | 13 |
|
|
22 | 28 |
|
23 | 29 | Output: True |
24 | 30 |
|
25 | | - Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].*/ |
| 31 | + Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0]. |
| 32 | + */ |
| 33 | + |
26 | 34 | publicclass_456 { |
27 | 35 |
|
28 | 36 | /**Looked at this post: https://discuss.leetcode.com/topic/67881/single-pass-c-o-n-space-and-time-solution-8-lines-with-detailed-explanation |
29 | 37 | * It scans only once, this is the power of using correct data structure. |
30 | | - * It goes from the right to the left. It keeps pushing elements into the stack, but it also keeps poping elements out of the stack as long as the current element is bigger than this number.*/ |
| 38 | + * It goes from the right to the left. |
| 39 | + * It keeps pushing elements into the stack, |
| 40 | + * but it also keeps poping elements out of the stack as long as the current element is bigger than this number.*/ |
31 | 41 | publicstaticbooleanfind132pattern(int[]nums) { |
32 | | -Stack<Integer>stack =newStack(); |
| 42 | +Deque<Integer>stack =newLinkedList<>(); |
33 | 43 |
|
34 | 44 | ints3 =Integer.MIN_VALUE; |
35 | 45 | for (inti =nums.length-1;i >=0;i--){ |
36 | 46 | if (nums[i] <s3)returntrue; |
37 | | -elsewhile (!stack.isEmpty() &&nums[i] >stack.peek()){ |
38 | | -s3 =Math.max(s3,stack.pop()); |
| 47 | +else { |
| 48 | +while (!stack.isEmpty() &&nums[i] >stack.peek()){ |
| 49 | +s3 =Math.max(s3,stack.pop()); |
| 50 | + } |
39 | 51 | } |
40 | 52 | stack.push(nums[i]); |
41 | 53 | } |
|