leetcode 300 Solution

代码解析

package com.demo.s300;


/**
 *给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 *
 * 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-increasing-subsequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
public int lengthOfLIS(int[] nums) {
        if(nums.length == 0) {
        return 0;
        }
        int size = 1;
        //严格递增子序列数组
        int[] sub = new int[nums.length+1];
        //初始化第0个节点
        sub[size] = nums[0];
        int pos = 0;
        //遍历数组nums
        for(int i= 1; i< nums.length; i++) {
        //前一个小于后一个节点时，记录到sub数组
        if(sub[size] < nums[i]) {
        sub[++size] = nums[i];
        } else {
        //重置sub数组，分左右两个指针判断
        int l = 1;
        int r = size;
        //如果sub中找不到比nums[i]小的元素则从0开始替换
        pos = 0;
        //移动两边指针
        while(l <= r) {
        //取中间点
        int mid = (l + r) >> 1;
        //因为sub已经有序，所以二分法，找到满足升序的中间点pos，更新sub数组
        if(sub[mid] <  nums[i]) {
        l = mid + 1;
        pos = mid;
        } else {
        r = mid - 1;
        }
        }
        //更新sub数组
        sub[pos + 1] = nums[i];
        }
        }
        return size;
        }

        }