Chương trình tìm độ dài của danh sách con dài nhất trong đó sự khác biệt giữa tối thiểu và tối đa nhỏ hơn k trong Python

Giả sử chúng ta có một danh sách các số được gọi là num và một giá trị khác k, chúng ta phải tìm độ dài của danh sách con dài nhất trong đó sự khác biệt tuyệt đối giữa phần tử lớn nhất và nhỏ nhất là ≤ k.

Vì vậy, nếu đầu vào là nums =[2, 4, 6, 10] k =4, thì đầu ra sẽ là 3, vì chúng ta có thể chọn pick [2, 4, 6] ở đây sự khác biệt tuyệt đối là 4.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo maxd hai hàng đợi kết thúc kép, lưu ý
• i:=0, res:=1
• đối với mỗi chỉ số j và giá trị a trong A, thực hiện
  • trong khi maxd không phải là 0 và a> phần tử cuối cùng của maxd, hãy thực hiện
    • xóa phần tử cuối cùng khỏi maxd
  • trong khi tâm trí không phải là 0 và
  • xóa phần tử cuối cùng khỏi tâm trí
• chèn một vào cuối maxd
• chèn vào cuối tâm trí
• while maxd [0] - mind [0]> limit, do
  • nếu maxd [0] giống với A [i], thì
    • xóa mục từ bên trái của maxd
  • nếu tâm [0] giống với A [i], thì
    • xóa mục khỏi tâm trí
  • i:=i + 1
• res:=tối đa res và (j - i + 1)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

[2, 4, 6, 10], 4

Đầu ra

3