สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และ k ตอนนี้ ให้พิจารณาการดำเนินการที่เราสามารถเพิ่มองค์ประกอบใดองค์ประกอบหนึ่งได้เพียงครั้งเดียว หากเราสามารถดำเนินการได้มากถึง k ครั้ง เราต้องหารายการย่อยที่ยาวที่สุดที่มีองค์ประกอบเท่ากัน
ดังนั้นหากอินพุตเป็นเหมือน nums =[3, 5, 9, 6, 10, 7] k =6 ผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถเพิ่ม 9 หนึ่งครั้งและ 6 สี่ครั้งเพื่อรับรายการย่อย [10, 10 , 10].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ถ้าตัวเลขว่างก็
-
คืนค่า 0
-
-
wMax :=คิวสิ้นสุดคู่ที่มีขนาดเท่ากับ nums และใส่คู่ (nums[0], 0)
-
ผม :=0, inc :=0
-
สำหรับ j ในช่วง 1 ถึงขนาดของ nums ทำ
-
ในขณะที่ wMax ไม่ว่างเปล่าและ wMax[0, 1]
-
ลบองค์ประกอบด้านซ้ายของ wMax
-
-
pMax :=wMax[0, 0]
-
ในขณะที่ wMax ไม่ว่างเปล่าและองค์ประกอบแรกของรายการสุดท้ายของ wMax <=nums[j] ให้ทำ
-
ลบองค์ประกอบที่ถูกต้องออกจาก wMax
-
-
แทรก (nums[j], j) ต่อท้าย wMax
-
ถ้า pMax
-
inc =inc + (j - i) * (wMax[0, 0] - pMax)
-
-
มิฉะนั้น
-
inc :=inc + pMax - nums[j]
-
-
ถ้า inc> k แล้ว
-
inc :=inc - wMax[0, 0] - nums[i]
-
ในขณะที่ wMax ไม่ว่างเปล่าและ wMax[0, 1] <=i ทำ
-
ลบองค์ประกอบด้านซ้ายของ wMax
-
-
ถ้า wMax[0, 0]
-
inc =inc - (nums[i] - wMax[0, 0]) * (j - i)
-
-
ผม :=ผม + 1
-
-
-
ขนาดส่งคืนของ nums - i
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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[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))
อินพุต
[3, 5, 9, 6, 10, 7], 6
ผลลัพธ์
3
