โปรแกรมหาความยาวสับลิสต์ยาวสุดที่ความต่าง min-max ≤ k ใน Python

สมมติว่ามีรายการตัวเลข nums และค่า k ต้องการหาความยาวสับลิสต์ (subarray) ยาวที่สุดที่ความต่างสัมบูรณ์ระหว่างค่ามากที่สุดและน้อยที่สุด ≤ k

ตัวอย่าง: nums = [2, 4, 6, 10], k = 4 ผลลัพธ์ 3 เลือก [2, 4, 6] ความต่าง 4

ขั้นตอนการแก้ปัญหา

1. ใช้ deque 2 ตัว: maxd (เก็บค่ามากสุด), mind (เก็บค่าน้อยสุด)
2. i = 0, res = 1
3. วน j, a ใน enumerate(A):
   • ขณะ maxd และ a > maxd[-1]: maxd.pop()
   • ขณะ mind และ a < mind[-1]: mind.pop()
   • เพิ่ม a เข้า maxd และ mind
   • ขณะ maxd[0] - mind[0] > limit:
     • ถ้า maxd[0] == A[i]: maxd.popleft()
     • ถ้า mind[0] == A[i]: mind.popleft()
     • i += 1
   • res = max(res, j - i + 1)
4. คืน res

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

from collections import deque, defaultdict

class Solution:
    def solve(self, A, limit):
        maxd = deque()
        mind = deque()
        i = 0
        res = 1
        for j, a in enumerate(A):
            while maxd and a > maxd[-1]:
                maxd.pop()
            while mind and a < mind[-1]:
                mind.pop()
            maxd.append(a)
            mind.append(a)
            while maxd[0] - mind[0] > limit:
                if maxd[0] == A[i]:
                    maxd.popleft()
                if mind[0] == A[i]:
                    mind.popleft()
                i += 1
            res = max(res, j - i + 1)
        return res

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

อินพุต

[2, 4, 6, 10], 4

เอาต์พุต

3