สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums เราต้องหาความยาวของรายการย่อยที่ยาวที่สุด โดยที่ 2 * รายการย่อยขั้นต่ำ> สูงสุดของรายการย่อย
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[10, 2, 6, 6, 4, 4] ผลลัพธ์จะเป็น 4 เนื่องจากรายการย่อย [6, 6, 4,4] เป็นรายการย่อยที่ยาวที่สุดที่มีเกณฑ์ เป็น 2 * 4> 6.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้-
-
ยกเลิก :=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
-
-
ret :=สูงสุดของ ret และ (r - l)
-
-
รีเทิร์น
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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))
อินพุต
[10, 2, 6, 6, 4, 4]
ผลลัพธ์
4
