Chương trình tìm dãy con cạnh tranh nhất (most competitive) trong Python

Cho mảng nums và k. Dãy con s1 cạnh tranh hơn s2 (cùng kích thước) nếu tại vị trí đầu tiên khác nhau, s1 có số nhỏ hơn. Tìm dãy con cạnh tranh nhất kích thước k.

Ví dụ: nums=[4,6,3,7], k=2 → [3,7]. Các dãy con size 2: [4,6],[4,3],[4,7],[6,3],[6,7],[3,7]. [3,7] nhỏ nhất theo từ điển.

Giải thuật (Stack đơn điệu)

1. attempts = len(nums) - k (số phần tử được bỏ).
2. Duyệt num trong nums:
   • Trong khi stack không rỗng, num < stack[-1], và attempts > 0: pop stack, attempts--.
   • Push num vào stack.
3. Trả về k phần tử đầu của stack.

Ví dụ minh họa

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]