题解 | #整数无序数组求第K大数#

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String res= br.readLine();
        br.close();
        String[]split=res.split(",");
        int arr[]=new int[split.length];
        for(int i=0;i<split.length;i++)arr[i]=Integer.parseInt(split[i].trim());
        System.out.println(helper(arr));
    }
/*
dp复杂度为n2
    private static int solve(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];   // dp[i]用于存储以nums[i]结尾的最长上升子序列的最大长度
        dp[0] = 1;
        int res=0;
        int max_sub=0;
        for(int i=0;i< nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            res=Math.max(res,dp[i]);

            }
        return res;
        }
 */
    //二分查找，维护最长子区间，并更新相应的值。
    //复杂度nLog(n)
    static int helper(int []arr){
        if(arr==null||arr.length==0)return 0;
        int n= arr.length;
        int []length_grow=new int[n];
        int index=1;
        length_grow[0]=arr[0];
        for(int i=1;i<n;i++){
            if(arr[i]>length_grow[index-1]){
                length_grow[index++]=arr[i];
                //System.out.println("新增："+arr[i]);
            }
            else{

                int j=lookup(length_grow,arr[i],0,index-1);
                //System.out.println("else:j="+j);
                length_grow[j]=arr[i];
            }
        }
        return index;
    }

    static int lookup(int []arr,int target,int left,int right){

        while(left<right){
            int mid=(right-left)/2+left;
            if(arr[mid]>=target)right=mid;
            else left=mid+1;
        }
        return left;
    }
}