โจทย์: กำหนดให้มีรายการตัวเลขชื่อ nums ต้องการหาความยาวของสับลิสต์ (Sublist/Subarray) ที่ยาวที่สุดที่ทำให้ 2 × (ค่าต่ำสุดของสับลิสต์) > (ค่าสูงสุดของสับลิสต์)
ตัวอย่าง
Input: nums = [10, 2, 6, 6, 4, 4]
Output: 4
เหตุผล: สับลิสต์ [6, 6, 4, 4] เป็นสับลิสต์ที่ยาวที่สุดที่ตรงเงื่อนไข (2×4) > 6 → 8 > 6 ✓
อัลกอริทึม: Sliding Window + Double-ended Queue (Deque)
ใช้เทคนิค Two Pointers (Two Pointers / Sliding Window) ร่วมกับ Deque สองอันเพื่อติดตามค่าต่ำสุดและค่าสูงสุดในหน้าต่างปัจจุบันอย่างมีประสิทธิภาพ O(n)
ขั้นตอนการทำงาน
- minq: Deque เก็บดัชนีของค่าต่ำสุด (ค่าจะเรียงจากน้อยไปมาก)
- maxq: Deque เก็บดัชนีของค่าสูงสุด (ค่าจะเรียงจากมากไปน้อย)
- ขยายหน้าต่างด้านขวา (
r) และอัปเดต Deque ทั้งสอง - หากเงื่อนไข
nums[minq[0]] * 2 <= nums[maxq[0]]ถูกละเมิด ให้ย่อหน้าต่างด้านซ้าย (l) - อัปเดตคำตอบสูงสุดตลอดเวลา
การใช้งาน Deque
minq: รักษาลำดับเพิ่มขึ้น (Increasing) - หัวคือค่าต่ำสุดmaxq: รักษาลำดับลดลง (Decreasing) - หัวคือค่าสูงสุด- เมื่อเพิ่มค่าใหม่ ให้ลบค่าที่ไม่เกี่ยวข้องออกจากท้าย Deque ก่อน
โค้ด Python
from collections import deque
def solve(nums):
ret = 0
minq, maxq = deque(), deque()
l, r = 0, 0
while r < len(nums):
n = nums[r]
# อัปเดต minq: รักษาลำดับเพิ่มขึ้น
while minq and n < nums[minq[-1]]:
minq.pop()
minq.append(r)
# อัปเดต maxq: รักษาลำดับลดลง
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)) # Output: 4ความซับซ้อน
- Time Complexity: O(n) - แต่ละองค์ประกอบถูกเพิ่มและลบจาก Deque สูงสุด 1 ครั้ง
- Space Complexity: O(n) - สำหรับ Deque และตัวแปรช่วย
การทดสอบเพิ่มเติม
# ทดสอบกรณีต่างๆ
print(solve([1, 2, 3, 4, 5])) # 2 (เช่น [1,2] หรือ [2,3] ฯลฯ)
print(solve([5, 4, 3, 2, 1])) # 5 (ทั้งอาร์เรย์ 2*1 > 5? ไม่ 2*1=2 < 5... ต้องทดสอบจริง)
print(solve([10, 10, 10, 10])) # 4 (2*10 > 10 ✓)
print(solve([])) # 0