leetcode/code/lc300.java at master · mJackie/leetcode · GitHub

History

49 lines (47 loc) · 1.94 KB

Raw

package code;

* 300. Longest Increasing Subsequence

* 题意：最长递增子数组，不一定是连续的

* 难度：Medium

* 分类：Binary Search, Dynamic Programming

* 思路：基本的思路是dp[i]记录以nums[i]结尾的最长长度，每次遍历 dp[i] 得到dp[i+1]，复杂度为O(n^2)。最优的解法是O(nlgn)，dp[i]是递增的数组，每次插入时二分查找是lgn。

* Tips：经典题目，记一下

* lc132

import java.util.Arrays;

public class lc300 {

public int lengthOfLIS(int[] nums) {

if(nums.length<2)

return nums.length;

int[] dp = new int[nums.length]; //dp[i] 存储以nums[i]结尾的最大长度

Arrays.fill(dp,1); //记住fill 1

int res = 1;

for (int i = 1; i < nums.length ; i++) {

for (int j = 0; j < i ; j++) {

if(nums[i]>nums[j]){

dp[i] = Math.max(dp[j]+1, dp[i]);

}

res = Math.max(res, dp[i]);

}

return res;

}

public int lengthOfLIS2(int[] nums) {

if(nums.length<2)

return nums.length;

int size = 0; //size指dp中递增的长度。 dp[0~i] 表示了长度为 i+1 的递增子数组，且最后一个值是最小值

int[] dp = new int[nums.length]; //dp存储递增的数组，之后更新这个数组。如果x>最后一个值，则插入到末尾，否则更新对应位置上的值为该值。

for (int i = 0; i < nums.length ; i++) {

int left = 0;

int right = size;

while(left!=right){ //得到要插入的位置

int mid = (left+right)/2;

if(dp[mid]<nums[i]) left = mid+1; //这是+1记住，不能到else去-1, 会死循环。+1就超出边界，后续用left赋值

else right = mid;

}

dp[left] = nums[i];

if(left==size) size++;

}

return size;

}

leetcode/code/lc300.java at master · mJackie/leetcode · GitHub

Expand file tree

Breadcrumbs

lc300.java

Latest commit

History

Breadcrumbs

lc300.java

File metadata and controls