4ms O(nlogn) non-recursive easy to understand java solution


  • 7
    L
    public int lengthOfLIS(int[] nums) {
        List<Integer> seq = new ArrayList<>(nums.length);     
    
        for(int num: nums){
            if(   seq.size()              == 0
               || seq.get(seq.size() - 1) <  num  ){                
               seq.add(num);
            }else{
                seq.set(binarySearch(seq, num - 0.5), num);
            }
        }      
    
        return seq.size();
    }
    
    private int binarySearch(List<Integer> seq, double target){
        int st  = 0;
        int ed  = seq.size() - 1;
        int mid = 0;    
    
        while(st <= ed){
            mid = st + (ed - st)/2;
            
            if(seq.get(mid) > target){
                ed = mid - 1;
            }else{
                st = mid + 1;
            }
        }
        
        return st;
    }

Log in to reply
 

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