สมมติว่าเรามีอาร์เรย์ของอุณหภูมิที่เป็นบวกซึ่งแสดงถึงอุณหภูมิ T ภารกิจคือการคำนวณว่าจะมีอุณหภูมิที่อุ่นกว่าในครั้งต่อไปกี่วันในรายการที่กำหนด
ตัวอย่าง
อินพุต-1: T =[ 73, 74, 75, 71, 69, 72, 76, 73]
ผลลัพธ์: [1, 1, 4, 2, 1 ,1 ,0,0]
คำอธิบาย: ในรายการอุณหภูมิที่กำหนด [73, 74, 75, 71, 69, 72, 76, 73] อุณหภูมิที่สูงขึ้นถัดไปคือวันที่ 1 ในทำนองเดียวกัน วันที่ 6 เป็นอุณหภูมิที่อบอุ่นที่สุดในทั้งหมด ดังนั้น เอาต์พุตจะเป็น [ 1, 1, 4, 2, 1, 1, 0, 0].
แนวทางในการแก้ปัญหานี้
เรามีรายการอุณหภูมิและเราต้องคำนวณจำนวนวันจนถึงวันที่อากาศอบอุ่นถัดไปจากอุณหภูมิที่กำหนด
เพื่อแก้ปัญหานี้ เราสามารถใช้ Stack เริ่มแรกสแต็กว่างเปล่า และเราจะตรวจสอบว่าด้านบนของสแต็กว่างเปล่าหรือไม่ จากนั้นจึงดันอุณหภูมิ ต่อไป หากอุณหภูมิที่ด้านบนของปึกน้อยกว่าอุณหภูมิที่มีอยู่ถัดไป แสดงว่าเย็นกว่า และเราจะดึงออกจากสแต็ค
เราจะตรวจสอบอีกครั้งว่าส่วนบนสุดของปึกมีอุณหภูมิสูงขึ้นหรืออุ่นขึ้น จากนั้นคำนวณวันโดยลบวันออกจากมันและเก็บดัชนีไว้ในผลลัพธ์
- ป้อนข้อมูลอุณหภูมิ
- ฟังก์ชันจำนวนเต็ม dailyTemperature(int *T) ใช้อาร์เรย์อุณหภูมิเป็นอินพุตและส่งคืนรายการอุณหภูมิที่ร้อนที่สุดถัดไป
- วนซ้ำเหนืออาร์เรย์อุณหภูมิ
- สร้างเวกเตอร์ผลลัพธ์หรืออาร์เรย์เพื่อส่งคืนรายการอุณหภูมิทั้งหมด
- สร้างสแต็กเปล่าแล้วดันอุณหภูมิในขณะที่ตรวจสอบว่า top()>T[i] จากนั้นดันเข้าไปในสแต็กแล้วคำนวณวัน
- จัดเก็บผลลัพธ์และส่งคืน
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
void dailyTemp(int * T, int n) {
stack < int > s;
int ans[n];
memset(ans, 0, sizeof(ans));
for (int i = 0; i < n; i++) {
while (!s.empty() && T[s.top()] < T[i]) {
int j = s.top();
s.pop();
ans[j] = i - j;
}
s.push(i);
}
for (int i = 0; i < n; i++) {
cout << ans[i] << " " << ;
}
}
int main() {
int n = 8;
int T[8] = {73, 74, 75, 71, 69, 72, 76, 73};
dailyTemp(T, n);
return 0;
} ผลลัพธ์
การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์เป็น
1 1 4 2 1 1 0 0
อุณหภูมิที่อุ่นขึ้นถัดไปในอุณหภูมิที่กำหนดคือวันที่ 4
