Chương trình tìm độ dài danh sách con dài nhất có chênh lệch max-min ≤ k trong Python

Mô tả bài toán

Cho danh sách nums và giá trị k. Tìm độ dài danh sách con liên tiếp dài nhất mà hiệu giữa giá trị lớn nhất và nhỏ nhất ≤ k.

Ví dụ: nums = [2, 4, 6, 10], k = 4 → đầu ra 3 (danh sách con [2,4,6]).

Giải thuật (Cửa sổ trượt + Deque đơn điệu)

1. Sử dụng hai deque maxd (giảm dần) và mind (tăng dần) để theo dõi max/min trong cửa sổ.
2. Khởi tạo i = 0, res = 1.
3. Duyệt j từ 0 đến n-1:
   • Cập nhật maxd và mind với a = nums[j].
   • Khi maxd[0] - mind[0] > k: thu hẹp cửa sổ từ trái (i++), xóa phần tử khỏi deque nếu cần.
   • Cập nhật res = max(res, j - i + 1).
4. Trả về res.

Ví dụ mã Python

from collections import deque

class Solution:
    def solve(self, A, limit):
        maxd = deque()
        mind = deque()
        i = 0
        res = 1
        for j, a in enumerate(A):
            while maxd and a > maxd[-1]:
                maxd.pop()
            while mind and a < mind[-1]:
                mind.pop()
            maxd.append(a)
            mind.append(a)
            while maxd[0] - mind[0] > limit:
                if maxd[0] == A[i]:
                    maxd.popleft()
                if mind[0] == A[i]:
                    mind.popleft()
                i += 1
            res = max(res, j - i + 1)
        return res

ob = Solution()
nums = [2, 4, 6, 10]
k = 4
print(ob.solve(nums, k))

Đầu vào

[2, 4, 6, 10], 4

Đầu ra

3