โปรแกรมค้นหาความยาวของรายการย่อยที่ยาวที่สุดพร้อมเงื่อนไขช่วงค่าใน Python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums เราต้องหาความยาวของรายการย่อยที่ยาวที่สุดโดยที่ 2 * (รายการย่อยขั้นต่ำ)> (รายการย่อยสูงสุด)

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[10, 2, 6, 6, 4, 4] ผลลัพธ์จะเป็น 4 เนื่องจากรายการย่อย [6, 6, 4, 4] เป็นรายการย่อยที่ยาวที่สุดที่ตรงตามที่กำหนด เกณฑ์ (2*4)> 6.

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

• ret :=0
• minq :=คิวดับเบิ้ลสิ้นสุดที่ว่างเปล่า
• maxq :=คิวดับเบิ้ลสิ้นสุดที่ว่างเปล่า
• l :=0
• r :=0
• ในขณะที่ r <ขนาดของ nums ทำ
  • n :=nums[r]
  • ในขณะที่ minq ไม่ว่างเปล่าและ n
  • ลบองค์ประกอบสุดท้ายออกจาก minq
• แทรก r ที่ส่วนท้ายของ minq
• ในขณะที่ maxq ไม่ว่างเปล่าและ n> nums[องค์ประกอบสุดท้ายของ maxq] ให้ทำ
  • ลบองค์ประกอบสุดท้ายออกจาก maxq
• แทรก r ที่ส่วนท้ายของ maxq
• r :=r + 1
• ในขณะที่ l
• ถ้า minq[0] เหมือนกับ l แล้ว
  • รายการซ้ายจาก minq
• ถ้า maxq[0] เหมือนกับ l แล้ว
  • ลบรายการสุดท้ายของ maxq
• l :=l + 1

ตัวอย่าง

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

from collections import deque
def solve(nums):
   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

nums = [10, 2, 6, 6, 4, 4]
print(solve(nums))

อินพุต

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

ผลลัพธ์

4