Java Concise Method in O(n) Time


  • 1
    W
    
    public class Solution {
        public boolean find132pattern(int[] nums) {
            int []big=findCloestGreater(nums);
            boolean res=findSmaller(nums,big);
            return res;
        }
        public int[] findCloestGreater(int[]nums){
            int []res=new int[nums.length];
            Stack<Integer>s=new Stack<>(); 
            for(int i=0;i<nums.length;i++){
                if(!s.isEmpty()){
                    while(!s.isEmpty()&&nums[s.peek()]<=nums[i]) s.pop();
                    if(!s.isEmpty()) res[i]=s.peek();
                }
                s.push(i);
            }
            return res;
        }
        public boolean findSmaller(int[]nums,int[] big){
            int min=Integer.MAX_VALUE;
            for(int i=1;i<big.length;i++){
                if(big[i]==0) continue;
                for(int j=big[i-1];j<big[i];j++)
                    min=Math.min(nums[j],min);
                if(min<nums[i]) return true;
            }
            return false;
        }
    }
    

  • 0
    X

    duuuuuuuuuu, great


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.