Chương trình tìm phần tử lớn hơn đầu tiên về phía phải (vòng tròn) trong Python

Cho danh sách nums, với mỗi chỉ mục i tìm phần tử đầu tiên bên phải (quay vòng về đầu danh sách) lớn hơn nums[i]. Nếu không có, đặt -1.

Ví dụ

Đầu vào: [4, 5, 1, 3].
Đầu ra: [5, -1, 3, 4].

Thuật toán

1. Khởi tạo stack chứa 0, kết quả res kích thước n toàn -1.
2. Lặp 2 lần qua mảng:
   • Với i từ 0 đến n-1:
     • Khi stack không rỗng và a[stack[-1]] < a[i]: res[stack.pop()] = a[i].
     • Push i vào stack.
3. Trả về res.

Mã nguồn Python

class Solution:
    def solve(self, a):
        n = len(a)
        stack, res = [0], [-1] * n
        for _ in range(2):
            for i in range(n):
                while stack and a[stack[-1]] < a[i]:
                    res[stack[-1]] = a[i]
                    stack.pop()
                stack.append(i)
        return res

ob = Solution()
nums = [4, 5, 1, 3]
print(ob.solve(nums))

Đầu vào / Đầu ra

Input: [4, 5, 1, 3]
Output: [5, -1, 3, 4]