数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：查找最长子序列，其中每两个相邻元素之间的绝对差值最多为k。
假设我们给定一个数字列表和另一个值k。我们的任务是找到最长子序列的长度，其中每两个相邻元素之间的绝对差值最多为k。
因此，如果输入类似于 nums = [5, 6, 2, 1, -6, 0, -1], k = 4，则输出将为6。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 update()。它将接收 i, x 作为参数。
i := i + n
当 i 非零时，执行以下操作：
segtree[i] := segtree[i] 和 x 的最大值
i := i / 2
定义一个函数 query()。它将接收 i, j 作为参数。
ans := -infinity
i := i + n
j := j + n + 1
当 i < j 且非零时，执行以下操作：
如果 i mod 2 等于 1，则
ans := ans 和 segtree[i] 的最大值
i := i + 1
如果 j mod 2 等于 1，则
j := j - 1
ans := ans 和 segtree[j] 的最大值
i := i / 2
j := j / 2
返回 ans
现在，在主函数中，执行以下操作：
nums = [5, 6, 2, 1, -6, 0, -1]
k = 4
n = 2 的 (log₂(len(nums) + 1) + 1) 次幂
segtree := [0] * 100000
snums := 对列表 nums 进行排序
index := 创建一个集合，其中 x: i 对应于 snums 中的每个索引 i 和元素 x
ans := 0
对于 nums 中的每个 x，执行以下操作：
lo := 在 snums 中返回最左边的位置，在此位置可以插入 (x - k) 并保持排序顺序
hi := (在 snums 中返回最左边的位置，在此位置可以插入 (x + k) 并保持排序顺序) - 1
count := query(lo, hi)
update(index[x], count + 1)
ans := ans 和 (count + 1) 的最大值
返回 ans
让我们来看下面的实现，以便更好地理解：
示例
import math, bisect
class Solution:
def solve(self, nums, k):
n = 2 ** int(math.log2(len(nums) + 1) + 1)
segtree = [0] * 100000
def update(i, x):
i += n
while i:
segtree[i] = max(segtree[i], x)
i //= 2
def query(i, j):
ans = −float("inf")
i += n
j += n + 1
while i < j:
if i % 2 == 1:
ans = max(ans, segtree[i])
i += 1
if j % 2 == 1:
j −= 1
ans = max(ans, segtree[j])
i //= 2
j //= 2
return ans
snums = sorted(nums)
index = {x: i for i, x in enumerate(snums)}
ans = 0
for x in nums:
lo = bisect.bisect_left(snums, x − k)
hi = bisect.bisect_right(snums, x + k) − 1
count = query(lo, hi)
update(index[x], count + 1)
ans = max(ans, count + 1)
return ans
ob = Solution()
print(ob.solve([5, 6, 2, 1, −6, 0, −1], 4))输入
[5, 6, 2, 1, −6, 0, −1], 4
输出
6
浏览量：391
