Python程序：查找最长子列表，其中最小值和最大值之间的差小于k

假设我们有一个名为nums的数字列表和另一个值k，我们需要找到最长子列表的长度，其中最大元素和最小元素之间的绝对差≤k。

因此，如果输入类似于nums = [2, 4, 6, 10] k = 4，则输出将为3，因为我们可以选择[2, 4, 6]，这里绝对差为4。

为了解决这个问题，我们将遵循以下步骤：

• 创建两个双端队列maxd，mind
• i := 0，res := 1
• 对于每个索引j和值a在A中，执行以下操作：
  • 当maxd不为空且a > maxd的最后一个元素时，执行以下操作：
    • 从maxd删除最后一个元素
  • 当mind不为空且a < mind的最后一个元素时，执行以下操作：
    • 从mind删除最后一个元素
  • 将a插入到maxd的末尾
  • 将a插入到mind的末尾
  • 当maxd[0] - mind[0] > limit时，执行以下操作：
    • 如果maxd[0]与A[i]相同，则
      • 从maxd的左侧删除项目
    • 如果mind[0]与A[i]相同，则
      • 从mind的左侧删除项目
    • i := i + 1
  • res := res和(j - i + 1)中的最大值
• 返回res

让我们看看下面的实现以更好地理解：

示例

 实时演示

from collections import deque, defaultdict
class Solution:
   def solve(self, A, limit):
      maxd = deque()
      mind = deque()
      i = 0
      res = 1
      for j, a in enumerate(A):
         while maxd and a > maxd[-1]:
            maxd.pop()
         while mind and a < mind[-1]:
            mind.pop()
         maxd.append(a)
         mind.append(a)
         while maxd[0] - mind[0] > limit:
            if maxd[0] == A[i]:
               maxd.popleft()
            if mind[0] == A[i]:
               mind.popleft()
            i += 1
            res = max(res, j - i + 1)
      return res
ob = Solution()
nums = [2, 4, 6, 10]
k = 4
print(ob.solve(nums, k))

输入

[2, 4, 6, 10], 4

输出

3

Arnab Chakraborty

更新于: 2020年11月19日

199 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习