Daily Temperatures

Bài toán

Cho một mảng các số nguyên temperatures biểu thị nhiệt độ hàng ngày. Trả về một mảng answer sao cho answer[i] là số ngày bạn phải chờ để có nhiệt độ ấm hơn. Nếu không có ngày nào ấm hơn trong tương lai, answer[i] = 0.

Ví dụ:

Input: [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]

Phân Tích & Tiếp Cận

Cách 1: Brute Force

Với mỗi ngày i, chạy vòng lặp j từ i+1 đến hết để tìm ngày đầu tiên ấm hơn.

• $O(n^2)$. Quá chậm nếu $N \approx 10^5$.

Cách 2: Monotonic Decreasing Stack (Ngăn xếp đơn điệu giảm)

Mục tiêu: Với mỗi ngày, ta muốn biết "Ai là người đầu tiên bên phải lớn hơn mình?".

Ta dùng Stack để lưu index của những ngày chưa tìm được ngày ấm hơn. Quy tắc: Stack luôn chứa các nhiệt độ theo thứ tự GIẢM DẦN (tính từ đáy lên đỉnh). Tại sao?

• Nếu stack đang là [75, 71, 69] (đỉnh là 69).
• Ngày tiếp theo là 72.
• Vì 72 > 69: Ngày 69 đã tìm thấy "cứu tinh" của đời mình. Pop 69 ra, tính khoảng cách.
• Stack còn [75, 71]. Đỉnh là 71.
• Vì 72 > 71: Ngày 71 cũng tìm thấy cứu tinh. Pop 71 ra.
• Stack còn [75]. Đỉnh 75.
• 72 < 75: Ngày 75 vẫn chưa tìm được ai ấm hơn. Push 72 vào để chờ đợi tiếp.
• Stack giờ là [75, 72] (Vẫn đảm bảo giảm dần).

function dailyTemperatures(temperatures: number[]): number[] {
    const n = temperatures.length;
    const res: number[] = new Array(n).fill(0);
    const stack: number[] = []; // Stack lưu INDEX

    for (let i = 0; i < n; i++) {
        const currentTemp = temperatures[i];

        // Nếu nhiệt độ hiện tại "nóng" hơn cái đang chờ trên đỉnh stack
        while (stack.length > 0 && currentTemp > temperatures[stack[stack.length - 1]]) {
            const prevIndex = stack.pop()!;
            // Tính số ngày chờ đợi
            res[prevIndex] = i - prevIndex;
        }

        stack.push(i);
    }

    return res;
}

• Time Complexity: $O(n)$. Mỗi phần tử được Push vào Stack 1 lần và Pop ra tối đa 1 lần.
• Space Complexity: $O(n)$.

Pattern Nhận Diện

Monotonic Stack (Stack đơn điệu) là một vũ khí cực mạnh cho các bài toán dạng:

• Tìm Next Greater Element (Phần tử lớn hơn tiếp theo).
• Tìm Next Smaller Element.
• Tính diện tích biểu đồ (Largest Rectangle in Histogram).

Bất cứ khi nào bạn cần tìm phần tử "gần nhất" thỏa mãn điều kiện lớn/nhỏ hơn, hãy nghĩ đến Monotonic Stack.