โปรแกรมหาความยาวซับลิสต์ยาวที่สุดที่ 2×min > max ใน Python

สมมติว่าเรามีรายการตัวเลข nums หาความยาวซับลิสต์ (subarray ติดกัน) ยาวที่สุดที่ 2 * min(sublist) > max(sublist)

ตัวอย่าง: nums = [10, 2, 6, 6, 4, 4] ผลลัพธ์ 4 (ซับลิสต์ [6, 6, 4, 4] เพราะ 2×4 > 6)

ขั้นตอนการแก้ปัญหา (Sliding Window + Deque)

1. ret = 0
2. สร้าง deque minq (เก็บ index ค่าเพิ่มขึ้น) และ maxq (เก็บ index ค่าลดลง)
3. l = 0, r = 0
4. วนลูป while r < len(nums):
   • n = nums[r]
   • รักษา minq: while minq และ n < nums[minq[-1]]: minq.pop() แล้ว minq.append(r)
   • รักษา maxq: while maxq และ n > nums[maxq[-1]]: maxq.pop() แล้ว maxq.append(r)
   • r += 1
   • while l < r และ nums[minq[0]] * 2 <= nums[maxq[0]]:
     • ถ้า minq[0] == l: minq.popleft()
     • ถ้า maxq[0] == l: maxq.popleft()
     • l += 1
   • ret = max(ret, r - l)
5. คืนค่า ret

ตัวอย่างโค้ด Python

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

อินพุต / เอาต์พุต

Input: [10, 2, 6, 6, 4, 4]

Output: 4