資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：查詢K次遞增後的最長等值子列表
假設我們有一個名為nums的數字列表和一個整數k。現在，考慮一個操作，我們可以將任何一個元素遞增一次。如果我們最多可以執行k次操作，我們必須找到包含相等元素的最長子列表。
因此，如果輸入類似於nums = [3, 5, 9, 6, 10, 7] k = 6，則輸出將為3，因為我們可以將9遞增一次，將6遞增四次以獲得子列表[10, 10, 10]。
為了解決這個問題，我們將遵循以下步驟：
如果nums為空，則
返回0
wMax := 一個大小與nums相同的雙端佇列，並插入一個對(nums[0], 0)
i := 0, inc := 0
對於j從1到nums的大小，執行
當wMax不為空且wMax[0, 1] < i時，執行
刪除wMax的左元素
pMax := wMax[0, 0]
當wMax不為空且wMax的最後一個元素的第一個元素 <= nums[j]時，執行
從wMax刪除右元素
在wMax的末尾插入(nums[j], j)
如果pMax < wMax[0, 0]，則
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] < nums[i]，則
inc = inc - (nums[i] - wMax[0, 0]) * (j - i)
i := 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
更新於：2020年10月10日
瀏覽量：116
廣告