Mô phỏng thuật toán Nhiệt độ ngày (stack đơn điệu)

Daily Temperatures · Nhóm: Ngăn xếp & Hàng đợi

Với mỗi ngày, tìm còn bao nhiêu ngày nữa thì gặp ngày ấm hơn bằng ngăn xếp đơn điệu giảm.

Ý tưởng

Ngăn xếp lưu chỉ số các ngày còn chờ ngày ấm hơn, nhiệt độ giảm dần từ đáy lên đỉnh.

Khi ngày hiện tại ấm hơn đỉnh ngăn xếp, pop đỉnh ra và ghi khoảng cách ngày làm đáp án.

Đẩy ngày hiện tại vào, những ngày còn kẹt lại cuối cùng có đáp án 0.

Vì sao đúng

Mỗi ngày chỉ vào và ra ngăn xếp đúng một lần, khi bị pop nghĩa là vừa tìm được ngày ấm hơn gần nhất phía sau.

Mã Python

def daily_temperatures(temps):
    n = len(temps)
    answer = [0] * n
    stack = []                       # indices, temps decreasing
    for i in range(n):
        while stack and temps[i] > temps[stack[-1]]:
            j = stack.pop()          # day j finally sees a warmer day
            answer[j] = i - j
        stack.append(i)
    return answer

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.