Chương trình tìm danh sách con tương đương dài nhất sau khi tăng K trong Python

Giả sử chúng ta có một danh sách các số được gọi là nums và k. Bây giờ, hãy xem xét một hoạt động trong đó wecan tăng một phần tử bất kỳ một lần. Nếu chúng ta có thể thực hiện các thao tác nhiều nhất k lần, chúng ta phải tìm ra danh sách con dài nhất chứa các phần tử bằng nhau.

Vì vậy, nếu đầu vào giống như nums =[3, 5, 9, 6, 10, 7] k =6, thì đầu ra sẽ là 3, vì chúng ta tăng 9 một lần và 6 bốn lần để có được danh sách con [10, 10 , 10].

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

• nếu nums trống, thì

  • trả về 0

• wMax:=một hàng đợi kết thúc kép có kích thước giống như nums. và chèn một cặp (nums [0], 0)

• i:=0, inc:=0

• đối với j trong phạm vi 1 đến kích thước của nums, thực hiện

  • trong khi wMax không trống và wMax [0, 1]

    • xóa phần tử bên trái của wMax

  • pMax:=wMax [0, 0]

  • trong khi wMax không trống và phần tử đầu tiên của mục cuối cùng của wMax <=nums [j], do

    • xóa phần tử bên phải khỏi wMax

  • insert (nums [j], j) vào cuối wMax

  • nếu pMax

    • inc =inc + (j - i) * (wMax [0, 0] - pMax)

  • nếu không,

    • inc:=inc + pMax - nums [j]

  • nếu inc> k, thì

    • inc:=inc - wMax [0, 0] - nums [i]

    • trong khi wMax không trống và wMax [0, 1] <=i, do

      • xóa phần tử bên trái của wMax

    • nếu wMax [0, 0]

      • inc =inc - (nums [i] - wMax [0, 0]) * (j - i)

    • i:=i + 1

• kích thước trả về của nums - i

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

Đầu vào

[3, 5, 9, 6, 10, 7], 6

Đầu ra

3