1ms Java solution without binarySearch and with O(1) space


  • 0
    X

    The idea is very simple,just search from potential start point, during each search find the next potential start point.
    public class Solution {

    public int lengthOfLIS(int[] nums) {
        int len=nums.length;
        if(len<=1){
            return len;
        }
        Queue<Integer> queue=new LinkedList<Integer>();
        int max=1;
        queue.offer(0);
        while(!queue.isEmpty()){
            int start=queue.poll();
            if(len-start<max){
                break;
            }
            int maxSub=1;
            int lastmin=Integer.MIN_VALUE;
            int curmin=nums[start];
            for(int i=start+1;i<len;i++){
                if(nums[i]<curmin&&nums[i]>lastmin){
                    curmin=nums[i];
                }else if(nums[i]>curmin){
                    maxSub++;
                    lastmin=curmin;
                    curmin=nums[i];
                }else if(nums[i]<lastmin){
                    if(queue.isEmpty()){
                        queue.offer(i);
                    }
                }
            }
            max=Math.max(max,maxSub);
        }
        return max;
    }
    

    }


Log in to reply
 

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