Python 中 K 次递增后查找最长等效子列表的程序

pythonserver side programmingprogramming更新于 2026/1/23 21:32:17

假设我们有一个名为 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))