TreeMap Java Solution O(n log n)


  • 0
    X

    Same idea as DP and Binary Search. It uses TreeMap to keep the previous lengths in the DP collection sorted.

    public class Solution {
        public int lengthOfLIS(int[] nums) {
            TreeMap<Integer, Integer> map = new TreeMap<>(Collections.reverseOrder());
            for(int i = 0; i < nums.length; i++) {
                boolean smallestForNow = true;
                for(int len: map.keySet()) {
                    if(nums[map.get(len)] < nums[i]) {
                        smallestForNow = false;
                        if(!map.containsKey(len + 1) || nums[i] < nums[map.get(len + 1)])
                            map.put(len + 1, i);
                        break;
                    }
                }
                if(smallestForNow) map.put(1, i);
            }
            if(map.isEmpty()) return 0;
            else return map.firstKey();
        }
    }
    

Log in to reply
 

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