300. 最长递增子序列
- 思路
- example
- 子序列：不需要连续, LIS
- 单串DP
dp[i]: 以ith结尾
- 复杂度. 时间：
, 空间:
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = [0] * len(nums)
dp[0] = 1
for i in range(1, len(nums)):
dp[i] = 1
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
dp = [1 for _ in range(n)]
res = dp[0]
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
res = max(res, dp[i])
return res
- 贪心+二分(左边界），时间
dp[i]: 长度为i的LIS的最后一个元素的最小可能值。这样就能构造尽可能长的递增子序列。
初始化dp[0] = float('-inf')
dp是严格递增的 （单调栈?)
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
def BinarySearch_insert(dp, target):
left, right = 0, len(dp)-1
while left <= right:
mid = left + (right - left) // 2
if dp[mid] > target:
right = mid - 1
elif dp[mid] < target:
left = mid + 1
else: # nums[mid] == target
right = mid - 1
return left # it's possible to have left = len(dp) + 1
n = len(nums)
dp = [float('-inf')]
res = 0
for i in range(n):
# 在dp中找最小的index使得dp[index] >= nums[i], 二分找左边界
insert_idx = BinarySearch_insert(dp, nums[i])
if insert_idx == len(dp):
dp.append(nums[i])
res += 1
else:
dp[insert_idx] = nums[i]
return res
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
def binarySearch(dp, target):
n = len(dp)
left, right = 0, n-1
while left <= right:
mid = left + (right - left) // 2
if dp[mid] < target:
left = mid + 1
elif dp[mid] > target:
right = mid - 1
else:
right = mid - 1
return left
n = len(nums)
dp = [-float('inf')]
for i in range(n):
idx = binarySearch(dp, nums[i])
if idx == len(dp):
dp.append(nums[i])
dp[idx] = nums[i]
return len(dp)-1
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
dp = [-float('inf')]
for i in range(n):
idx = bisect_left(dp, nums[i])
if idx == len(dp):
dp.append(nums[i])
else:
dp[idx] = nums[i]
return len(dp) - 1
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
def BinarySearch(nums, target):
n = len(nums)
left, right = 0, n-1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
n = len(nums)
stack = [nums[0]]
for i in range(1, n):
idx = BinarySearch(stack, nums[i])
if idx == len(stack):
stack.append(nums[i])
else:
stack[idx] = nums[i]
return len(stack)
674. 最长连续递增序列
- 思路
- example
- 连续子序列, LCIS
dp[i]：以ith结尾
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
n = len(nums)
dp = [1 for _ in range(n)]
dp[0] = 1
for i in range(1, n):
if nums[i] > nums[i-1]:
dp[i] = dp[i-1] + 1
return max(dp)
- 滑窗
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
n = len(nums)
left, right = 0, 1
res = 1
while right < n:
if nums[right] > nums[right-1]:
res = max(res, right - left + 1)
else:
left = right
right += 1
return res
- 贪心
- 小结：连续问题--当前状态只跟前一步有关；不连续问题--当前状态跟前几步有关。
718. 最长重复子数组
- 思路
- example
- 连续子序列
- 两个数组匹配，二维DP
dp[i][j]: nums1 以ith结尾，nums2以 jth结尾
如果nums1[i] != nums2[j],那么dp[i][j] = 0.
- 复杂度. 时间：O(mn), 空间: O(mn)
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
m, n = len(nums1), len(nums2)
dp =[[0] * n for _ in range(m)]
res = 0
for j in range(n):
if nums1[0] == nums2[j]:
dp[0][j] = 1
res = 1
for i in range(m):
if nums1[i] == nums2[0]:
dp[i][0] = 1
res = 1
for i in range(1, m):
for j in range(1, n):
if nums1[i] == nums2[j]:
dp[i][j] = dp[i-1][j-1] + 1
res = max(res, dp[i][j])
return res
- 可空间优化
- 可以定义dp size (m+1)*(n+1), 简化初始化过程
# dp[i][j]: 以i-1结尾，j-1结尾的最长公共后缀的长度
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
m, n = len(nums1), len(nums2)
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
dp[0][0] = 0
res = 0
for i in range(1, m+1):
for j in range(1, n+1):
if nums1[i-1] == nums2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
res = max(res, dp[i][j])
return res
354. 俄罗斯套娃信封问题
- 思路
- example
- 注意：长宽相同无法嵌套 (严格包含才能套）
- 二维 LIS
对宽度 w 从小到大排序，确保了 w 这个维度可以互相嵌套
当宽度w相同时，按h从大到小排序，确保LIS不会出现宽度w相同的情况 (否则在同一宽度情况下，会有嵌套关系。)
按以上方法排序后只保留h维度，运用一维LIS方法找LIS即可
- 复杂度. 时间：O(n logn), 空间: O(n)
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
def LIS(nums):
n = len(nums)
dp = [-float('inf')]
for i in range(n):
idx = bisect_left(dp, nums[i])
if idx == len(dp):
dp.append(nums[i])
dp[idx] = nums[i]
return len(dp)-1
envelopes.sort(key=lambda x: (x[0], -x[1]))
return LIS([x[1] for x in envelopes])
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
def LIS(nums):
n = len(nums)
dp = [-float('inf')]
for i in range(n):
index = bisect_left(dp, nums[i])
if index == len(dp):
dp.append(nums[i])
dp[index] = nums[i]
return len(dp) - 1
envelopes.sort(key=lambda x: (x[0], -x[1]))
return LIS([x[1] for x in envelopes])
