程序在Python中增加K后找到最长的等效子列表

假设我们有一个称为nums和k的数字列表。现在，考虑一个操作，我们可以一次增加任意一个元素。如果我们最多可以执行k次操作，则必须找到包含相等元素的最长子列表。

因此，如果输入像nums = [3、5、9、6、10、7] k = 6，则输出将为3，因为我们可以将9一次递增，而6则递增4次以获得子列表[10 10，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