Chương trình tìm độ dài dãy con dài nhất thỏa 2*min > max bằng Python

Cho danh sách nums, tìm độ dài dãy con liên tiếp dài nhất thỏa mãn 2 * min(sublist) > max(sublist).

Ví dụ: nums = [10, 2, 6, 6, 4, 4] → 4 (dãy con [6, 6, 4, 4], vì 2*4 > 6).

Quy trình giải quyết (Sliding Window + Deque)

1. Dùng hai deque minq (tăng dần) và maxq (giảm dần) để theo dõi min/max cửa sổ.
2. Mở rộng cửa sổ bên phải r, cập nhật deque.
3. Thu hẹp cửa sổ bên trái l cho đến khi 2 * nums[minq[0]] > nums[maxq[0]].
4. Cập nhật độ dài lớn nhất ret = max(ret, r - l).

Ví dụ mã nguồn

class Solution:
    def solve(self, nums):
        from collections import deque
        ret = 0
        minq, maxq = deque(), deque()
        l, r = 0, 0
        while r < len(nums):
            n = nums[r]
            while minq and n < nums[minq[-1]]:
                minq.pop()
            minq.append(r)
            while maxq and n > nums[maxq[-1]]:
                maxq.pop()
            maxq.append(r)
            r += 1
            while l < r and nums[minq[0]] * 2 <= nums[maxq[0]]:
                if minq[0] == l:
                    minq.popleft()
                if maxq[0] == l:
                    maxq.popleft()
                l += 1
            ret = max(ret, r - l)
        return ret

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

Đầu vào

[10, 2, 6, 6, 4, 4]

Đầu ra

4