最长递增子序列问题
本节课讲述：最长递增子序列 & 最长不下降子序列的最优解，以及一些扩展题目
备注
本节课讲述的是最优解，时间复杂度是 ，空间复杂度 ，好实现、理解难度不大
这个问题也可以用线段树来求解，时间和空间复杂度和本节讲的最优解没有区别，但需要理解线段树
线段树会在【扩展】课程阶段讲述
题目1.最长递增子序列
题目描述
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
提示：
1 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4
测试链接
普通解法的动态规划
dp[i]：以 i 结尾的最长递增子序列长度
递推：从左往右，每个位置等于左边位置比当前小的数的结果 +1 的最大值
func lengthOfLIS(nums []int) int {
n := len(nums)
ans := 0
// dp[i]: 以 i 为结尾的最长递增子序列
dp := make([]int, n)
for i := 0; i < n; i++ {
// 初始化：最长递增子序列最短只有当前一个数
dp[i] = 1
// 找左边位置比当前小的数
for j := 0; j < i; j++ {
if nums[j] < nums[i] {
dp[i] = max(dp[i], dp[j]+1)
}
}
ans = max(ans, dp[i])
}
return ans
}- 时间复杂度
- 空间复杂度
最优解
dp[i]：以i结尾的最长递增子序列长度ends[i]：目前所有长度为i+1的递增子序列的最小结尾数字
递推：从左往右，靠二分 ends 递推
func lengthOfLIS(nums []int) int {
n := len(nums)
// ends[i]: 目前所有长度为 i+1 的递增子序列的最小结尾数字
ends := make([]int, n)
// endLen 表示 ends 数组目前的有效区长度
// 也就是最长递增子序列的长度，这个值就是答案，没必要写 dp 数组了
// ends[0:endLen] 是有效区，有效区内的数字一定严格升序
endLen := 0
for i := 0; i < n; i++ {
// 二分搜索 ends 有效区中 >= nums[i] 的最左位置
find := bs1(ends, endLen, nums[i])
if find == -1 {
// 没找到：说明当前数 nums[i] 比之前的数都大
// 长度为 endLen+1 的递增子序列目前只有这一个，最小结尾数字就是它
ends[endLen] = nums[i]
// 最长递增子序列长度 +1
endLen++
} else {
// 找到了：说明最长递增子序列不会变长
// 长度为 find+1 的递增子序列最小结尾数字更新
ends[find] = nums[i]
}
}
return endLen
}
// 最长递增子序列：
// nums[:length] 是严格升序的，找到 >= target 的最左位置
// 如果不存在返回 -1
func bs1(nums []int, length, target int) int {
l, r := 0, length-1
ans := -1
for l <= r {
m := l + (r-l)>>1
if nums[m] >= target {
ans = m
r = m - 1
} else {
l = m + 1
}
}
return ans
}- 时间复杂度
- 空间复杂度
扩展：最长不下降子序列
只要将 最优解 的二分改成找 > target 的最左位置即可。不找等于，相等的时候就会找不到，就会扩充 ends 有效区，也就是最长不下降子序列长度
// 最长不下降子序列：
// nums[:length] 是不降序的，找到 > target 的最左位置
// 如果不存在返回 -1
func bs2(nums []int, length, target int) int {
l, r := 0, length-1
ans := -1
for l <= r {
m := l + (r-l)>>1
if nums[m] > target {
ans = m
r = m - 1
} else {
l = m + 1
}
}
return ans
}题目2.俄罗斯套娃信封问题
题目描述
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
提示：
1 <= envelopes.length <= 10^5envelopes[i].length == 21 <= wi, hi <= 10^5
测试链接
思路
题目转化为：信封按宽度从小到大、相同宽度按高度从大到小排序，求排序后数组的高度最长递增子序列长度
答案
func maxEnvelopes(envelopes [][]int) int {
sort.Slice(envelopes, func(i, j int) bool {
if envelopes[i][0] == envelopes[j][0] {
return envelopes[i][1] >= envelopes[j][1]
}
return envelopes[i][0] < envelopes[j][0]
})
n := len(envelopes)
ends := make([]int, n)
endLen := 0
for i := 0; i < n; i++ {
find := bs(ends, endLen, envelopes[i][1])
if find == -1 {
ends[endLen] = envelopes[i][1]
endLen++
} else {
ends[find] = envelopes[i][1]
}
}
return endLen
}
func bs(nums []int, length, target int) int {
l, r := 0, length-1
ans := -1
for l <= r {
m := l + (r-l)>>1
if nums[m] >= target {
ans = m
r = m - 1
} else {
l = m + 1
}
}
return ans
}题目3.使数组 K 递增的最少操作次数
题目描述
给你一个下标从 0 开始包含 n 个正整数的数组 arr ，和一个正整数 k 。
如果对于每个满足 k <= i <= n-1 的下标 i ，都有 arr[i-k] <= arr[i] ，那么我们称 arr 是 K 递增 的。
- 比方说，
arr = [4, 1, 5, 2, 6, 2]对于k = 2是 K 递增的，因为：arr[0] <= arr[2] (4 <= 5)arr[1] <= arr[3] (1 <= 2)arr[2] <= arr[4] (5 <= 6)arr[3] <= arr[5] (2 <= 2)
- 但是，相同的数组
arr对于k = 1不是 K 递增的（因为arr[0] > arr[1]），对于k = 3也不是 K 递增的（因为arr[0] > arr[3]）。
每一次 操作 中，你可以选择一个下标 i 并将 arr[i] 改成任意 正整数。
请你返回对于给定的 k ，使数组变成 K 递增的 最少操作次数 。
提示：
1 <= arr.length <= 10^51 <= arr[i], k <= arr.length
测试链接
思路
每一组的最少操作次数 = 该组长度 - 该组最长不下降子序列长度
最后将每一组的最少操作次数相加就是答案
答案
func kIncreasing(arr []int, k int) int {
n := len(arr)
// n / k 向上取整
nums := make([]int, (n+k-1)/k)
size := 0
ans := 0
for i := 0; i < k; i++ {
size = 0
for j := i; j < n; j += k {
nums[size] = arr[j]
size++
}
ans += size - lengthOfNoDecreasing(nums, size)
}
return ans
}
// nums[:size] 中的最长不下降子序列长度
func lengthOfNoDecreasing(nums []int, size int) int {
ends := make([]int, size)
endLen := 0
for i := 0; i < size; i++ {
find := bs(ends, endLen, nums[i])
if find == -1 {
ends[endLen] = nums[i]
endLen++
} else {
ends[find] = nums[i]
}
}
return endLen
}
func bs(nums []int, length, target int) int {
l, r := 0, length-1
ans := -1
for l <= r {
m := l + (r-l)>>1
if nums[m] > target {
ans = m
r = m - 1
} else {
l = m + 1
}
}
return ans
}题目4.最长数对链
题目描述
给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。
现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。
找出并返回能够形成的 最长数对链的长度 。
你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例 1：
输入：
pairs = [[1,2], [2,3], [3,4]]输出：
2解释：最长的数对链是
[1,2] -> [3,4]。
示例 2：
输入：
pairs = [[1,2],[7,8],[4,5]]输出：
3解释：最长的数对链是
[1,2] -> [4,5] -> [7,8]。
提示：
n == pairs.length1 <= n <= 1000-1000 <= lefti < righti <= 1000
测试链接
思路
ends 进行比较的数和进入 ends 的数不同
答案
func findLongestChain(pairs [][]int) int {
// 数对根据开始位置从小到大排序，结束位置无所谓
sort.Slice(pairs, func(i, j int) bool {
return pairs[i][0] < pairs[j][0]
})
n := len(pairs)
ends := make([]int, n)
endLen := 0
for i := 0; i < n; i++ {
// 拿开始位置去查，保证当前开始位置 > 之前结束位置
find := bs(ends, endLen, pairs[i][0])
if find == -1 {
// 放入结束位置
ends[endLen] = pairs[i][1]
endLen++
} else {
ends[find] = min(ends[find], pairs[i][1])
}
}
return endLen
}
func bs(nums []int, length, target int) int {
l, r := 0, length-1
ans := -1
for l <= r {
m := l + (r-l)>>1
if nums[m] >= target {
ans = m
r = m - 1
} else {
l = m + 1
}
}
return ans
}题目5.有一次修改机会的最长不下降子序列
题目描述
给定一个长度为 n 的数组 arr，和一个整数 k
只有一次机会可以将其中连续的 k 个数全修改成任意一个值
这次机会你可以用也可以不用，请返回最长不下降子序列长度
数据规模：
1 <= k, n <= 10^51 <= arr[i] <= 10^6
测试链接
思路
答案
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
const (
MAXN = 1e5
)
var (
n int
k int
arr = [MAXN]int{}
ends = [MAXN]int{}
right = [MAXN]int{}
)
func main() {
// s := `5 1
// 1 4 2 8 5`
// in := bufio.NewScanner(strings.NewReader(s))
in := bufio.NewScanner(os.Stdin)
in.Split(bufio.ScanWords)
out := bufio.NewWriterSize(os.Stdout, 4096)
for in.Scan() {
n, _ = strconv.Atoi(in.Text())
in.Scan()
k, _ = strconv.Atoi(in.Text())
for i := 0; i < n; i++ {
in.Scan()
arr[i], _ = strconv.Atoi(in.Text())
}
if k >= n {
fmt.Fprintln(out, n)
} else {
fmt.Fprintln(out, compute())
}
}
out.Flush()
}
func compute() int {
calcRight()
endLen := 0
ans := 0
for i, j := 0, k; j < n; i, j = i+1, j+1 {
// 查阶段：拿划分值 arr[j] 查
find := bs2(endLen, arr[j])
left := 0
if find == -1 {
// 整个左侧都比 arr[j] 小
left = endLen
} else {
left = find
}
ans = max(ans, left+k+right[j])
// 入阶段：入 i 位置数
find = bs2(endLen, arr[i])
if find == -1 {
ends[endLen] = arr[i]
endLen++
} else {
ends[find] = arr[i]
}
}
// 右侧无数的情况
ans = max(ans, endLen+k)
return ans
}
// 生成辅助数组 right
// right[j]：一定以 arr[j] 做开头的情况下，arr[j:] 上最长不下降子序列长度是多少
// 关键逻辑：
// 一定以 arr[j] 做开头的情况下，arr[j:] 上最长不下降子序列
// 就是从 n-1 出发来看（从右往左遍历)，以 arr[j] 做结尾的情况下的最长不上升子序列
func calcRight() {
endLen := 0
for i := n - 1; i >= 0; i-- {
find := bs1(endLen, arr[i])
if find == -1 {
ends[endLen] = arr[i]
endLen++
right[i] = endLen
} else {
ends[find] = arr[i]
right[i] = find + 1
}
}
}
// 求最长不上升子序列长度的二分
// ends[:length]是降序的，找到 <target 的最左位置
// 不存在返回 -1
func bs1(length, target int) int {
l, r := 0, length-1
ans := -1
for l <= r {
m := l + (r-l)>>1
if ends[m] < target {
ans = m
r = m - 1
} else {
l = m + 1
}
}
return ans
}
// 求最长不下降子序列长度的二分
// ends[:length]是升序的，找到 >target 的最左位置
// 不存在返回 -1
func bs2(length, target int) int {
l, r := 0, length-1
ans := -1
for l <= r {
m := l + (r-l)>>1
if ends[m] > target {
ans = m
r = m - 1
} else {
l = m + 1
}
}
return ans
}巧妙构思 VS. 成熟体系
673.最长递增子序列的个数：给定一个未排序的整数数组 nums，返回最长递增子序列的个数
这个问题的最优解能做到
会放在【扩展】课程阶段，详解树状数组（index tree）的时候来讲解，用这个高级数据结构来求解这个题会很方便
这里为什么要提呢？主要是想说：巧妙构思 VS. 成熟体系
- 这个问题用现阶段学过的内容也能解：有序表 + 前缀和，但是很麻烦
- 使用之后学的树状数组来解的话就非常方便
不能清楚数据结构和算法的整个体系，不了解一些高级的数据结构，用现有的知识来解决问题，可能就需要自己想一些巧妙的构思才可能解决；自己想好久的巧妙构思可能不如看一些新的数据结构和算法被启发到，原来很难的题、需要很多巧妙构思的题可能就是新数据结构和算法的模板题或者普通题
数据结构和算法的暴力美学，不是复杂度的暴力，而是保证复杂度最优的情况下思想变得异常简洁、异常美
想说的是：不要偏执于一隅，要先快速打通整个体系，在整个体系的基础上再进行深入和构思，才是更有意义的