โปรแกรมหารายการย่อยที่มีค่าเท่ากันมากที่สุดหลังเพิ่มค่าได้ K ครั้งใน Python

สมมติว่าเรามีรายการตัวเลข nums และค่า k พิจารณาการดำเนินการที่เราสามารถเพิ่มค่าขององค์ประกอบใดองค์ประกอบหนึ่งได้ 1 หน่วยต่อครั้ง หากเราสามารถดำเนินการได้สูงสุด k ครั้ง เราต้องการหารายการย่อยที่ยาวที่สุดที่มีองค์ประกอบเท่ากันทุกตัว

ตัวอย่างเช่น หาก nums = [3, 5, 9, 6, 10, 7] และ k = 6 ผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถเพิ่ม 9 หนึ่งครั้ง และ 6 สี่ครั้ง เพื่อได้รายการย่อย [10, 10, 10]

ขั้นตอนการแก้ปัญหา (Sliding Window + Deque)

1. หาก nums ว่าง ให้คืนค่า 0
2. ใช้ Deque wMax เก็บคู่ (value, index) เรียงตามค่ามากไปน้อย
3. กำหนด i = 0, inc = 0 (ค่าที่เพิ่มสะสม)
4. วนลูป j จาก 1 ถึง len(nums) - 1:
   • ลบองค์ประกอบซ้ายสุดของ wMax ที่มี index < i
   • pMax = wMax[0][0] (ค่าสูงสุดในหน้าต่างปัจจุบัน)
   • ลบองค์ประกอบขวาสุดของ wMax ที่มีค่า <= nums[j]
   • เพิ่ม (nums[j], j) เข้า wMax
   • คำนวณ inc ตามการเปลี่ยนแปลงของค่าสูงสุด
   • หาก k ให้ย่อหน้าต่างทางซ้าย (i += 1) และปรับ inc
5. คืนค่า len(nums) - i

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

from collections import deque

class Solution:
    def solve(self, nums, k):
        if not nums:
            return 0
        
        wMax = deque([(nums[0], 0)], maxlen=len(nums))
        i = 0
        inc = 0
        
        for j in range(1, len(nums)):
            while wMax and wMax[0][1] < i:
                wMax.popleft()
            
            pMax = wMax[0][0]
            
            while wMax and wMax[-1][0] <= nums[j]:
                wMax.pop()
            
            wMax.append((nums[j], j))
            
            if pMax < wMax[0][0]:
                inc += (j - i) * (wMax[0][0] - pMax)
            else:
                inc += pMax - nums[j]
            
            if inc > k:
                inc -= wMax[0][0] - nums[i]
                while wMax and wMax[0][1] <= i:
                    wMax.popleft()
                if wMax and wMax[0][0] < nums[i]:
                    inc -= (nums[i] - wMax[0][0]) * (j - i)
                i += 1
        
        return len(nums) - i

ob = Solution()
nums = [3, 5, 9, 6, 10, 7]
k = 6
print(ob.solve(nums, k))  # Output: 3

อินพุต

[3, 5, 9, 6, 10, 7], 6

เอาต์พุต

3