โปรแกรมค้นหาความยาวของรายการย่อยที่ยาวที่สุดโดยที่ความแตกต่างระหว่าง min และ max น้อยกว่า k ใน Python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และอีกค่าหนึ่งคือ k เราต้องหาความยาวของรายการย่อยที่ยาวที่สุดโดยที่ความแตกต่างที่แน่นอนระหว่างองค์ประกอบที่ใหญ่ที่สุดและน้อยที่สุดคือ ≤ k

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[2, 4, 6, 10] k =4 ผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถเลือกเลือก [2, 4, 6] ได้ ความแตกต่างแน่นอนคือ 4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้าง maxd คิวคู่สองคิวสูงสุด
• i :=0, res :=1
• สำหรับแต่ละดัชนี j และค่า a ใน A ให้ทำ
  • ในขณะที่ maxd ไม่ใช่ 0 และ a> องค์ประกอบสุดท้ายของ maxd ให้ทำ
    • ลบองค์ประกอบสุดท้ายออกจาก maxd
  • ขณะที่จิตไม่ใช่ 0 และ <ธาตุสุดท้ายของจิต จงทำ
    • ลบองค์ประกอบสุดท้ายออกจากใจ
  • ใส่ a ต่อท้าย maxd
  • ใส่ a ที่ส่วนท้ายของจิตใจ
  • ในขณะที่ maxd[0] - จิตใจ[0]> จำกัด ทำ
    • ถ้า maxd[0] เหมือนกับ A[i] แล้ว
      • ลบรายการจากด้านซ้ายของ maxd
    • ถ้าจิตใจ[0] เหมือนกับ A[i] แล้ว
      • ลบรายการออกจากด้านซ้ายของจิตใจ
    • ผม :=ผม + 1
  • res :=สูงสุดของ res และ (j - i + 1)
• ผลตอบแทน

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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