LeetCode递归篇

300. 最长递增子序列

复杂度最低的方法： 二分 + 贪心

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> g = new ArrayList<>();
        for (int x : nums){
            int j = lowerBound(g, x);
            if(j == g.size()){
                g.add(x);
            }
            else{
                g.set(j, x);
            }
        }
        return g.size();
    }

    private int lowerBound(List<Integer>g, int target){
        int left = -1, right = g.size(); // 开区间
        while (left + 1 < right){
            int mid = left + (right - left) / 2;
            if (g.get(mid) < target){
                left = mid;
            }
            else{
                right = mid;
            }
        }
        return right;
    }
}

初始化列表，g用于存储当前找到的最长递增子序列。不一定是实际的子序列，但长度是对的。

对数组nums中的每个元素 x 进行遍历，使用lowerBound方法找到x在g中的位置j。

如果j等于g的长度，说明x可以扩展当前的序列，把它添加到g的末尾；否则用x替换g中位置j的元素，以维持g的递增性质。

返回g的长度，这就是最长递增子序列的长度。

二分查找方法lowerBound用于找到第一个不小于target的元素位置。

Java中g.set(i, j)方法用于将g中下标为i的元素替换为j