2016年10月6日星期四

Smallest Number After Self

1.给一个int[]nums,返回int[] ans, ans[i]是i右边小于等于nums[i]的最大数,如果不存在,ans[i]=0

2.算法:
建立一个bst,找predecessor

      public static int[] biggestSmallerAfterSelf(int[] nums){  
           TreeSet<Integer> root = new TreeSet<>();  
           int[] ans = new int[nums.length];  
           for(int i = nums.length-1; i>=0; i--){  
                Integer pred = root.floor(nums[i]);  
                if(pred!=null){  
                     ans[i] = pred;  
                }  
                root.add(nums[i]);  
           }  
           return ans;  
      }  

没有评论:

发表评论