Nhiệt độ hàng ngày

Đề bài

Cho một mảng số nguyên temperatures đại diện cho nhiệt độ hàng ngày, trả về một mảng answer sao cho answer[i] là số ngày bạn cần chờ sau ngày thứ i để có được một ngày có nhiệt độ cao hơn. Nếu không có ngày nào trong tương lai có nhiệt độ cao hơn, giữ answer[i] == 0.

Ví dụ:
Ví dụ 1:

Đầu vào: temperatures = [73,74,75,71,69,72,76,73]
Đầu ra: [1,1,4,2,1,1,0,0]
Ví dụ 2:

Đầu vào: temperatures = [30,40,50,60]
Đầu ra: [1,1,1,0]
Ví dụ 3:

Đầu vào: temperatures = [30,60,90]
Đầu ra: [1,1,0]
Ràng buộc:
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
Giải pháp:
Bài toán yêu cầu chúng ta tìm số ngày cần chờ để có được một ngày có nhiệt độ cao hơn. Một cách tiếp cận hiệu quả là sử dụng một ngăn xếp để lưu trữ các chỉ số của các ngày trước đó mà chúng ta chưa tìm thấy nhiệt độ cao hơn.

Phương pháp:

Duyệt qua các phần tử trong mảng từ trái sang phải.
Sử dụng một ngăn xếp để lưu trữ các chỉ số của các ngày mà nhiệt độ chưa tìm thấy ngày nào cao hơn.
Với mỗi phần tử hiện tại, so sánh với nhiệt độ của các ngày được lưu trong ngăn xếp. Nếu nhiệt độ hiện tại cao hơn, cập nhật giá trị trong mảng answer cho các ngày trước đó.

Cách làm

#include <iostream>
#include <stack>
using namespace std;

void nhietDoHangNgay(int temperatures[], int n, int answer[]) {
    stack<int> st;

    for (int i = 0; i < n; i++) {
        // So sánh nhiệt độ hiện tại với nhiệt độ của các ngày trước đó được lưu trong ngăn xếp
        while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
            int idx = st.top();
            st.pop();
            answer[idx] = i - idx;
        }
        st.push(i);
    }

    // Với các ngày không có nhiệt độ cao hơn trong tương lai, answer[i] = 0
    while (!st.empty()) {
        answer[st.top()] = 0;
        st.pop();
    }
}

int main() {
    int temperatures[] = {73, 74, 75, 71, 69, 72, 76, 73};
    int n = sizeof(temperatures) / sizeof(temperatures[0]);
    int answer[n];

    nhietDoHangNgay(temperatures, n, answer);

    cout << "Cau tra loi: ";
    for (int i = 0; i < n; i++) {
        cout << answer[i] << " ";
    }
    cout << endl;

    return 0;
}