|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +importjava.util.Stack; |
| 4 | + |
| 5 | +publicclass_132Pattern { |
| 6 | +//a brute force method got TLE: |
| 7 | +publicbooleanfind132pattern_TLE(int[]nums) { |
| 8 | +for (inti =0;i <nums.length-2;i++){ |
| 9 | +for (intj =i+1;j <nums.length-1;j++){ |
| 10 | +if (nums[j] <nums[i])continue; |
| 11 | +for(intk =j+1;k <nums.length;k++){ |
| 12 | +if(nums[k] <nums[j] &&nums[i] <nums[k])returntrue; |
| 13 | + } |
| 14 | + } |
| 15 | + } |
| 16 | +returnfalse; |
| 17 | + } |
| 18 | + |
| 19 | + |
| 20 | +/**Looked at this post: https://discuss.leetcode.com/topic/67881/single-pass-c-o-n-space-and-time-solution-8-lines-with-detailed-explanation |
| 21 | + * It scans only once, this is the power of using correct data structure. |
| 22 | + * 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.*/ |
| 23 | +publicstaticbooleanfind132pattern(int[]nums) { |
| 24 | +Stack<Integer>stack =newStack(); |
| 25 | + |
| 26 | +ints3 =Integer.MIN_VALUE; |
| 27 | +for (inti =nums.length-1;i >=0;i--){ |
| 28 | +if (nums[i] <s3)returntrue; |
| 29 | +elsewhile (!stack.isEmpty() &&nums[i] >stack.peek()){ |
| 30 | +s3 =Math.max(s3,stack.pop()); |
| 31 | + } |
| 32 | +stack.push(nums[i]); |
| 33 | + } |
| 34 | + |
| 35 | +returnfalse; |
| 36 | + } |
| 37 | + |
| 38 | +publicstaticvoidmain (String...args){ |
| 39 | +int[]nums =newint[]{-1,3,2,0}; |
| 40 | +System.out.println(find132pattern(nums)); |
| 41 | + } |
| 42 | +} |