leetcode-300 - 动态规划 - leetcode

300. 最长递增子序列 🔍

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如， [3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1： 📝

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2： 📝

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3： 📝

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示： ⚠️

动态规划 💡

解题思路： 💡

状态定义 🎯
- 定义 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
- 初始状态：每个元素自身构成一个长度为 1 的递增子序列，即 dp[i] = 1
状态转移方程 🔄
- 对于每个位置 i，我们需要检查之前的所有位置 j (0 ≤ j < i)
- 如果 nums[i] > nums[j] ，说明可以将 nums [i] 接在以 nums [j] 结尾的递增子序列后面
- 状态转移方程： dp[i] = max(dp[i], dp[j] + 1)
具体步骤： 📝
- 初始化 dp 数组，所有元素设为 1
- 使用两层循环：
  - 外层循环遍历数组的每个位置 i
  - 内层循环遍历 i 之前的所有位置 j
- 如果 nums [i] > nums [j]，更新 dp [i]
- 最后遍历 dp 数组找出最大值
时间复杂度： ⏱️
- O (n²)，其中 n 是数组长度
- 需要两层循环，每层循环最多遍历 n 次
空间复杂度： 💾
- O (n)，需要一个长度为 n 的 dp 数组

	//lengthOfLIS 计算最长递增子序列的长度
	func lengthOfLIS(nums []int) int {
	// 初始化 dp 数组，dp [i] 表示以 nums [i] 结尾的最长递增子序列长度
	dp := make([]int,len(nums))
	// 初始时每个元素自身构成一个长度为 1 的递增子序列
	for i,_ := range dp{
	dp[i] = 1
	}

	// 遍历数组，计算每个位置的最长递增子序列长度
	for i := 0; i < len(nums); i++ {
	// 对于每个位置 i，检查之前的所有位置 j
	for j := 0; j < i; j++ {
	// 如果当前元素大于之前的元素，可以构成递增子序列
	if nums[i] > nums[j] {
	// 更新 dp [i] 为当前最长长度和以 j 结尾的长度 + 1 的较大值
	dp[i] = max(dp[i],dp[j]+1)
	}
	}
	}

	// 遍历 dp 数组找出最大值
	res := 0
	for i := 0; i < len(dp); i++{
	res = max(res,dp[i])
	}
	return res
	}

	//max 返回两个整数中的较大值
	func max(a int ,b int) int {
	if a > b {
	return a
	}
	return b
	}

# 二分法解法 🎯

解题思路： 💡

扑克牌分堆思想 🎴
- 将数组中的每个数字看作一张扑克牌
- 从左到右依次处理每张牌
- 对于每张牌，需要找到第一个牌堆顶大于当前牌的牌堆，将当前牌放在该牌堆顶
- 如果找不到合适的牌堆，则新建一个牌堆
为什么这样做是正确的？ 🤔
- 每个牌堆顶的牌都是严格递增的
- 牌堆的数量就是最长递增子序列的长度
- 通过二分查找可以快速找到合适的牌堆，时间复杂度为 O (nlogn)
具体步骤： 📝
- 初始化牌堆数组 top 和牌堆数量 piles
- 遍历数组中的每个数字
- 使用二分查找找到第一个牌堆顶大于当前数字的牌堆
- 如果找到合适的牌堆，将当前数字放在该牌堆顶
- 如果没找到合适的牌堆，新建一个牌堆
- 最终返回牌堆的数量
时间复杂度： ⏱️
- O (nlogn)，其中 n 是数组长度
- 每个数字都需要一次二分查找，二分查找的时间复杂度是 O (logn)
空间复杂度： 💾
- O (n)，需要一个长度为 n 的数组来存储牌堆

	func lengthOfLIS(nums []int) int {
	top := make([]int,len(nums))
	// 牌堆数初始化为 0
	piles := 0
	for i:=0; i<len(nums);i++{
	// 要处理的扑克牌
	poker := nums[i]
	// 搜索左侧边界的二分查找
	var left, right = 0,piles
	for left < right{
	mid := (left+right)/2
	if top[mid] > poker {
	right = mid
	}else if top[mid]< poker{
	left = mid + 1
	}else{
	right = mid
	}
	}
	// 没有找到合适的牌堆，新建一堆
	if left == piles{
	piles++
	}
	// 把这张牌放到牌堆顶
	top[left] = poker
	}
	// 牌堆数就是 LTS 长度
	return piles
	}