程序在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