Python - Tìm độ dài dãy con dài nhất thỏa mãn điều kiện giá trị

Cho danh sách số nums, tìm độ dài dãy con (sublist) liên tiếp dài nhất sao cho 2 × (giá trị nhỏ nhất) > (giá trị lớn nhất) trong dãy con đó.

Ví dụ

Input: nums = [10, 2, 6, 6, 4, 4]
Output: 4
Giải thích: Dãy con [6, 6, 4, 4] có min=4, max=6 → 2×4=8 > 6.

Thuật toán: Cửa sổ trượt với Deque đơn điệu

Sử dụng 2 deque để duy trì min và max trong cửa sổ hiện tại:

• minq: lưu chỉ số theo thứ tự giá trị tăng dần (đầu là min)
• maxq: lưu chỉ số theo thứ tự giá trị giảm dần (đầu là max)
• Mở rộng cửa sổ bên phải (r), cập nhật deque
• Nếu vi phạm điều kiện (2*min <= max), thu hẹp cửa sổ bên trái (l)
• Cập nhật kết quả tối đa

Mã Python

from collections import deque

def solve(nums):
    ret = 0
    minq, maxq = deque(), deque()
    l, r = 0, 0
    
    while r < len(nums):
        n = nums[r]
        
        # Duy trì minq tăng dần
        while minq and n < nums[minq[-1]]:
            minq.pop()
        minq.append(r)
        
        # Duy trì maxq giảm dần
        while maxq and n > nums[maxq[-1]]:
            maxq.pop()
        maxq.append(r)
        
        r += 1
        
        # Thu hẹp cửa sổ nếu vi phạm điều kiện
        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

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

Phân tích độ phức tạp

• Thời gian: O(n) - mỗi phần tử vào/ra deque tối đa 1 lần
• Không gian: O(n) - deque lưu tối đa n chỉ số

Áp dụng: Kỹ thuật này phổ biến trong các bài toán "cửa sổ trượt với điều kiện min/max" như LeetCode 1438, 2398.