程序在Python中增加K后找到最长的等效子列表
假设我们有一个称为nums和k的数字列表。现在，考虑一个操作，我们可以一次增加任意一个元素。如果我们最多可以执行k次操作，则必须找到包含相等元素的最长子列表。
因此，如果输入像nums=[3、5、9、6、10、7]k=6，则输出将为3，因为我们可以将9一次递增，而6则递增4次以获得子列表[1010，10]。
为了解决这个问题，我们将遵循以下步骤-
如果nums为空，则
返回0
wMax：=大小等于nums的双头队列。并插入一对（nums[0]，0）
i：=0，inc：=0
对于范围1至nums大小的j，执行
inc：=inc-wMax[0，0]-nums[i]
当wMax不为空且wMax[0，1]<=i时
如果wMax[0，0]<nums[i]，则
我：=我+1
删除wMax的左元素
inc=inc-（nums[i]-wMax[0，0]）*(j-i)
inc：=inc+pMax-数字[j]
inc=inc+(j-i)*（wMax[0，0]-pMax）
从wMax删除right元素
删除wMax的左元素
当wMax不为空且wMax[0，1]<i时
pMax：=wMax[0，0]
当wMax不为空且wMax的最后一项的第一个元素<=nums[j]时，执行
在wMax的末尾插入（nums[j]，j）
如果pMax<wMax[0，0]，则
除此以外，
如果inc>k，则
返回的数字大小-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