Chương trình tìm dãy con kích thước k chênh lệch min-max nhỏ nhất trong Python

Cho danh sách nums và số k. Chọn phần tử tạo dãy con sao cho chênh lệch giữa max và min nhỏ nhất. Trả về chênh lệch đó.

Ví dụ: nums = [3, 11, 6, 2, 9], → kết quả 4 (dãy [2, 3, 6]).

Giải thuật (Sắp xếp + Cửa sổ trượt O(n log n))

1. Sắp xếp .
2. Duyệt cửa sổ kích thước : với từ 0 đến , tính .
3. Trả về giá trị nhỏ nhất.

Ví dụ minh họa

class Solution:
    def solve(self, nums, k):
        nums.sort()
        ls = []
        for i in range(len(nums) - k + 1):
            ls.append(nums[i + k - 1] - nums[i])
        return min(ls)

ob = Solution()
nums = [3, 11, 6, 2, 9]
k = 3
print(ob.solve(nums, k))  # Output: 4

Đầu vào

[3, 11, 6, 2, 9], 3

Đầu ra

4