Giả sử chúng ta có một dãy nhiệt độ dương đại diện cho nhiệt độ T. Nhiệm vụ là tính xem còn bao nhiêu ngày nữa để nhiệt độ ấm hơn tiếp theo trong danh sách đã cho.
Ví dụ
Đầu vào-1: T =[73, 74, 75, 71, 69, 72, 76, 73]
Đầu ra: [1, 1, 4, 2, 1, 1, 0, 0]
Giải thích: Trong danh sách nhiệt độ đã cho [73, 74, 75, 71, 69, 72, 76, 73], nhiệt độ lớn hơn tiếp theo là ở Ngày 1. Tương tự, Ngày 6 là ấm nhất trong tất cả các nhiệt độ, do đó sản lượng sẽ là [1, 1, 4, 2, 1, 1, 0, 0].
Phương pháp tiếp cận để giải quyết vấn đề này
Chúng tôi có một danh sách các nhiệt độ và chúng tôi phải tính toán số ngày cho đến ngày ấm hơn tiếp theo từ các nhiệt độ đã cho.
Để giải quyết vấn đề này, chúng ta có thể sử dụng Stack. Ban đầu ngăn xếp trống, và chúng tôi sẽ kiểm tra xem trên cùng của ngăn xếp có trống không, sau đó đẩy nhiệt độ. Tiếp theo, nếu nhiệt độ trên cùng của ngăn xếp nhỏ hơn nhiệt độ hiện có tiếp theo, điều đó có nghĩa là nhiệt độ đó lạnh hơn và chúng tôi sẽ bật nó ra khỏi ngăn xếp.
Chúng tôi sẽ kiểm tra lại nếu phần trên cùng của ngăn xếp có nhiệt độ lớn hơn hoặc ấm hơn, sau đó tính ngày bằng cách trừ các ngày từ đó và lưu chỉ số trong kết quả.
- Nhận dữ liệu nhiệt độ đầu vào.
- Một hàm số nguyên dailyTempe Heat (int * T) lấy mảng nhiệt độ làm đầu vào và trả về danh sách nhiệt độ ấm nhất tiếp theo.
- Lặp lại trên mảng nhiệt độ.
- Tạo một mảng hoặc vectơ kết quả để trả về danh sách tất cả các nhiệt độ.
- Tạo một ngăn xếp trống và đẩy nhiệt độ trong khi kiểm tra xem top ()> T [i], sau đó đẩy nó vào ngăn xếp và tính toán ngày.
- Lưu trữ kết quả và trả lại.
Ví dụ
#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;
} Đầu ra
Chạy đoạn mã trên sẽ tạo ra kết quả là,
1 1 4 2 1 1 0 0
Nhiệt độ ấm hơn tiếp theo trong nhiệt độ đã cho là ở Ngày thứ 4.