Chương trình tìm kiếm thứ cạnh tranh nhất trong Python

Giả sử chúng ta có một nums mảng và một giá trị khác k, chúng ta phải tìm dãy con cạnh tranh nhất của các nums có kích thước k. Ở đây, một dãy con s1 cạnh tranh hơn một dãy con s2 (có kích thước bằng nhau) nếu ở vị trí đầu tiên mà s1 và s2 khác nhau, dãy con s1 có số nhỏ hơn số tương ứng trong s2.

Vì vậy, nếu đầu vào giống như nums =[4,6,3,7] k =2, thì đầu ra sẽ là [3,7] vì trong số tất cả các dãy con có kích thước 2, {[4,6], [4, 3], [4,7], [6,3], [6,7], [3,7]}, [3,7] là cạnh tranh nhất.

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

• lần thử:=kích thước của nums - k
• stack:=một danh sách mới
• đối với mỗi num trong nums, thực hiện
  • trong khi ngăn xếp không trống và num <đầu ngăn xếp và số lần thử> 0, thực hiện
    • phần tử pop từ ngăn xếp
    • nỗ lực:=nỗ lực - 1
  • đẩy num vào ngăn xếp
• trả về k phần tử hàng đầu của ngăn xếp

Ví dụ

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

def solve(nums, k):
   attempts = len(nums) - k
   stack = []
   for num in nums:
      while stack and num < stack[-1] and attempts > 0:
         stack.pop()
         attempts -= 1
      stack.append(num)

   return stack[:k]

nums = [4,6,3,7]
k = 2
print(solve(nums, k))

Đầu vào

[4,6,3,7], 2

Đầu ra

[3,7]