Daily Temperatures trong Python

Cho danh sách nhiệt độ hàng ngày T, trả về danh sách nơi mỗi phần tử cho biết phải đợi bao nhiêu ngày để gặp nhiệt độ cao hơn. Nếu không có ngày nào cao hơn, lưu 0.

Ví dụ: T = [73, 74, 75, 71, 69, 72, 76, 73] → [1, 1, 4, 2, 1, 1, 0, 0].

Giải thuật

• Khởi tạo mảng ans kích thước len(T) điền 0.
• Dùng stack lưu chỉ số, bắt đầu push 0, i = 1.
• Khi :
  • Khi stack không rỗng và T[i] > T[stack.top()]: pop, gán ans[idx] = i - idx.
  • Push i vào stack.
  • i++.
• Trả về ans.

Ví dụ code (Python)

class Solution:
    def dailyTemperatures(self, T):
        ans = [0] * len(T)
        stack = [0]
        i = 1
        while i < len(T):
            while stack and T[i] > T[stack[-1]]:
                idx = stack.pop()
                ans[idx] = i - idx
            stack.append(i)
            i += 1
        return ans

ob1 = Solution()
print(ob1.dailyTemperatures([73,74,75,71,69,72,76,73]))

Input

[73,74,75,71,69,72,76,73]

Output

[1, 1, 4, 2, 1, 1, 0, 0]