Java Patience Sort, Beat 99.80%.


  • 1

    Maybe this is faster is because I use a tricky binary search.

    public class Solution 
    {
        public int lengthOfLIS(int[] nums) 
        {
            if(nums.length == 0) return 0;
            
            
            int[] tails = new int[nums.length];
            int max = 0;
            tails[max] = Integer.MAX_VALUE;
            
            
            
            for(int i = 0; i< nums.length;i++)
            {
                if(nums[i] <= tails[0]) tails[0] = nums[i];
                else if(nums[i] >= tails[max]) tails[++max] = nums[i];
                else
                {
                    tails[binarySearch(0,max,tails,nums[i])] = nums[i];
                }
            }
            
            return max+1;
               
        }
        
        public int binarySearch(int L, int R, int[] tails, int target)
        {
            while(L <= R)
            {
                int M = L + (R - L)/2;
                
                if(target > tails[M]) L = M + 1;
                else R = M - 1;
            }
            
            return L;
        }
    }
    

    I won't talk about Patience Sort because there are so many documents about it.

    For this Binary Search:
    If the target value is in the array, it returns index of the target value.
    If the target value is not in the array, it returns the index of where it should be. That is just the tail index that we need.


  • 2

    @reboot329 said in Java Patience Sort, Beat 99.80%.:

    Maybe this is faster is because I use a tricky binary search.

    I think it's quite the opposite, that it's faster because you often don't use binary search. Looks like there are only some tiny test cases and three large ones: One is always increasing, one is always decreasing, and one is almost constant. In those test cases, you never do binary search, always get to use your shortcuts.


  • 0

    @StefanPochmann
    Indeed.
    Thank you for correcting my mistake.


Log in to reply
 

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