Chương trình tìm dãy con bằng nhau dài nhất sau K lần tăng trong Python

Cho danh sách nums và số k. Mỗi phép toán cho phép tăng một phần tử lên 1. Với tối đa k phép toán, tìm dãy con liên tiếp dài nhất mà sau khi tăng có thể làm cho tất cả phần tử bằng nhau.

Ví dụ: nums = [3, 5, 9, 6, 10, 7], k = 6 → kết quả 3 (tăng 9 lên 10, 6 lên 10 → dãy [10, 10, 10]).

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

Duy trì cửa sổ [i, j] và deque wMax lưu cặp (giá trị, chỉ số) giảm dần để lấy max O(1). Biến inc lưu tổng số lần tăng cần để đưa toàn bộ cửa sổ về giá trị max.

1. Khởi tạo wMax = deque([(nums[0], 0)]), i = 0, inc = 0.
2. Duyệt j từ 1 đến n-1:
   • Loại bỏ phần tử khỏi đầu deque nếu chỉ số < i.
   • Lưu pMax = wMax[0][0] (max cũ).
   • Thêm nums[j] vào deque (giữ tính đơn điệu giảm).
   • Cập nhật inc: nếu max mới lớn hơn max cũ → inc += (j - i) * (newMax - pMax); ngược lại → inc += pMax - nums[j].
   • Nếu k: thu hẹp cửa sổ từ trái (i++) và điều chỉnh inc.
3. Trả về n - i (độ dài cửa sổ lớn nhất tìm được).

Ví dụ minh họa

from collections import deque

class Solution:
    def solve(self, nums, k):
        if not nums:
            return 0
        wMax = deque([(nums[0], 0)], maxlen=len(nums))
        i = 0
        inc = 0
        for j in range(1, len(nums)):
            while wMax and wMax[0][1] < i:
                wMax.popleft()
            pMax = wMax[0][0]
            while wMax and wMax[-1][0] <= nums[j]:
                wMax.pop()
            wMax.append((nums[j], j))
            if pMax < wMax[0][0]:
                inc += (j - i) * (wMax[0][0] - pMax)
            else:
                inc += pMax - nums[j]
            if inc > k:
                inc -= wMax[0][0] - nums[i]
                while wMax and wMax[0][1] <= i:
                    wMax.popleft()
                if wMax[0][0] < nums[i]:
                    inc -= (nums[i] - wMax[0][0]) * (j - i)
                i += 1
        return len(nums) - i

ob = Solution()
nums = [3, 5, 9, 6, 10, 7]
k = 6
print(ob.solve(nums, k))  # Output: 3

Đầu vào

[3, 5, 9, 6, 10, 7], 6

Đầu ra

3