資料結構
網路
關係資料庫管理系統 (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
