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

开启你的职业生涯

完成课程获得认证

开始学习
广告