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

pythonserver side programmingprogramming

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

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

要解决这个问题，我们将遵循以下步骤 −

创建两个双端队列 maxd，注意
i := 0, res := 1
对于 A 中的每个索引 j 和值 a，执行
- 当 maxd 不为 0 且 a > maxd 的最后一个元素，执行
  - 从 maxd 中删除最后一个元素
- 当 mind 不为 0 且 a < mind 的最后一个元素时，执行
  - 从 mind 中删除最后一个元素
- 在 maxd 的末尾插入 a
- 在 mind 的末尾插入 a
- 当 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))