Daily Temperatures (อุณหภูมิรายวัน) ใน C++

โจทย์

กำหนด Array temperatures คืน Array answer ที่ answer[i] = จำนวนวันต้องรอจนกว่าจะเจออุณหภูมิสูงกว่า temperatures[i] ถ้าไม่มีให้ 0

ตัวอย่าง

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

Day 0 (73): วันถัดไป 74 > 73 → 1 day
Day 1 (74): วันถัดไป 75 > 74 → 1 day
Day 2 (75): รอ 4 วัน จน Day 6 (76) → 4 days
Day 3 (71): รอ 2 วัน จน Day 5 (72) → 2 days
Day 4 (69): วันถัดไป 72 > 69 → 1 day
Day 5 (72): รอ 1 วัน จน Day 6 (76) → 1 day
Day 6 (76): ไม่มีวันร้อนกว่า → 0
Day 7 (73): ไม่มีวันร้อนกว่า → 0
Output: [1, 1, 4, 2, 1, 1, 0, 0]

แนวคิด: Monotonic Stack (Decreasing)

Stack เก็บ Index ของวันที่ยังไม่เจออุณหภูมิสูงกว่า (Monotonically Decreasing Temperatures)

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

vector<int> dailyTemperatures(vector<int>& T) {
    int n = T.size();
    vector<int> ans(n, 0);
    stack<int> st; // Stack of indices
    
    for (int i = 0; i < n; i++) {
        // Current temp สูงกว่า Temp ที่ Stack Top
        while (!st.empty() && T[i] > T[st.top()]) {
            int idx = st.top(); st.pop();
            ans[idx] = i - idx; // ระยะห่างวัน
        }
        st.push(i);
    }
    // Stack ที่เหลือ = ไม่มีวันร้อนกว่า → ans = 0 (Initialized)
    return ans;
}

int main() {
    vector<int> T = {73, 74, 75, 71, 69, 72, 76, 73};
    auto ans = dailyTemperatures(T);
    
    for (int x : ans) cout << x << " ";
    cout << endl;
    
    // Test cases
    cout << "Test 2: ";
    for (int x : dailyTemperatures({30, 40, 50, 60})) cout << x << " "; // 1 1 1 0
    cout << endl;
    
    cout << "Test 3: ";
    for (int x : dailyTemperatures({30, 60, 90})) cout << x << " "; // 1 1 0
    cout << endl;
    
    return 0;
}

การทำงาน Step-by-Step

i=0, T=73: st=[0]
i=1, T=74: 74>73 → pop 0, ans[0]=1; st=[1]
i=2, T=75: 75>74 → pop 1, ans[1]=1; st=[2]
i=3, T=71: 71<75 → st=[2,3]
i=4, T=69: 69<71 → st=[2,3,4]
i=5, T=72: 72>69 → pop 4, ans[4]=1
         72>71 → pop 3, ans[3]=2
         72<75 → st=[2,5]
i=6, T=76: 76>72 → pop 5, ans[5]=1
         76>75 → pop 2, ans[2]=4
         st=[6]
i=7, T=73: 73<76 → st=[6,7]
End: ans[6]=0, ans[7]=0 (default)

Complexity

• Time: O(n) - แต่ละ Index Push/Pop สูงสุด 1 ครั้ง
• Space: O(n) - Stack + Answer Array

Variations

• Next Greater Element: คืนค่าอุณหภูมิ ไม่ใช่จำนวนวัน
• Previous Greater: กลับมาดูย้อนหลัง
• Circular Array: วนรอบ (LeetCode 503)

ผลลัพธ์

1 1 4 2 1 1 0 0
Test 2: 1 1 1 0
Test 3: 1 1 0

สรุป

Daily Temperatures = Classic Monotonic Stack Problem รูปแบบ Decreasing Stack เก็บ Index ที่ยังไม่เจอ Next Greater Element - LeetCode 739