Java O(n) Solution using Stack


  • 0
    H
    public int lengthOfLIS(int[] nums) {
        int len=nums.length;
        Stack<Integer> stack=new Stack<Integer>();
        for(int i=len-1; i>=0; i--)
        {
            if(stack.isEmpty())
            {
                stack.push(nums[i]);
            }else
            {
               int val= stack.pop();
               if(stack.isEmpty())
               {
                   if(nums[i]>=val)
                   {
                       val=nums[i];
                   }else
                   {
                	   stack.push(val);
                	   val=nums[i];
                   }
               }else
               {
                   int up=stack.peek();
                   if(nums[i]<val)
                   {
                       stack.push(val);
                       val=nums[i];
                   }else if(nums[i]>val && nums[i]<up)
                   {
                       val=nums[i];
                   }
               }
               stack.push(val);
            }
        }
        return stack.size();
    }

  • 0
    Y

    r u sure it is O(n)? What is the time complexity of ur stack.peek() function?


  • 0
    J

    stack.peek() means "Looks at the top of this stack", not "Finds the biggest one"


  • 0
    C

    This method don't get a correct answer on test case{11,12,13,14,15,6,7,8,101,18}。


  • 0
    K

    giving input as {1,3,6,7,9,4,10,5,6},you solution wrongly count the length of {1,3,4,5,6}.


  • 0

    Thanks, I have added the above test cases.


  • 0
    Y

    Ok. So it should not give a correct answer.


  • 0
    Y

    Your algorithm does not work if the LIS ends before nums[nums.length-2]


Log in to reply
 

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