LeetCode 300. Longest Increasing Subsequence (Tag:Binary Search)

1. 问题描述

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

翻译过来就是：给定一个输入的数组，返回递增的最大子序列的值。不要求子序列是连续的。

2. 解题思路

• 定义一个数组dp,用于存储当前扫描到的递增的数据
• len用于表示当前的递增子序列的长度
• 遍历数组
  • 使用二分查找法在dp中查找数据，确定数据的位置。
  • Arrays.binarySearch 返回的是查到的数据的坐标。若坐标为负值，则表示找不到数据，-7 表示 找不到数据，7 = dp数组的长度+1.
  • 在dp数组中放入数据
  • 若查到的数据的位置等于数组的dp的长度，表示子序列扩容，len自增1。
• 返回len。

3. 代码

class Solution {
   public int lengthOfLIS(int[] nums) {
       if (nums == null || nums.length == 0) {
           return 0;
       }
       int[] dp = new int[nums.length];
       int len = 0;
       for (int num : nums) {
           int i = Arrays.binarySearch(dp, 0, len, num);
           
           if (i < 0) {
               i = -(i + 1);
           }
           dp[i] = num;
           if(i == len) {
               len++;
           }
       }
       return len;
   }}