300. 最長(zhǎng)遞增子序列
Ⅰ、動(dòng)態(tài)規(guī)劃
-
代表前
個(gè)元素，以第
- 每次 遍歷一個(gè)
，更新
public class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] dp = new int[n];
dp[0] = 1;
int maxLen = 1;
for (int i = 1; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i])
dp[i] = Math.max(dp[i], dp[j] + 1);
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
}
Ⅱ遇八、二分查找 + 貪心
- 貪心思想：
- 順序遍歷一遍
矛绘，為了達(dá)到最長(zhǎng)的升序序列，盡可能取最小的值到
中
-
- 在升序
需要存放的位置揽碘，二分范圍
-
，可以直接插入到
在最后雳刺，此時(shí)“擴(kuò)容”
res++ -
二分找到最靠近前面位置的可插入位置，然后覆蓋插入裸违，不需要擴(kuò)容
-
- 順序遍歷一遍
- 準(zhǔn)備一個(gè)
掖桦，
即作為結(jié)果，同時(shí)也是二分查找的右邊界
- 最終的
res
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int res = 0;
for (int num : nums) {
int l = 0, r = res; // 確定好 tails 區(qū)間范圍
while (l < r) {
int mid = l + ((r - l) >>> 1);
if (num > tails[mid])
l = mid + 1;
else
r = mid;
}
tails[l] = num; // 當(dāng)前值替換二分找到的 l 位置
if (res == r) res++; // 需要“擴(kuò)容”
}
return res;
}
