প্রতিদিনের তাপমাত্রা দেওয়া আছে। প্রতিটি দিনের জন্য কতদিন পর তার চো বেসি তাপমাত্রা হবে তা বের করতে হবে। মনোটোনিক স্ট্যাক ব্যবহার করে O(n) সময়ে সমাধান করা যায়।
অ্যালগরিদম (Monotonic Stack)
- স্ট্যাকে ইনডেক্স রাখুন (তাপমাত্রা অনুযায়ী ডিক্রিজিং অর্ডার)।
- বর্তমান তাপমাত্রা স্ট্যাকের টপের চো বড় হলে, টপ পপ করুন এবং ans[top] = i - top।
- বর্তমান ইনডেক্স স্ট্যাকে পুশ করুন।
উদাহরণ
T = [73, 74, 75, 71, 69, 72, 76, 73]
আউটপুট: [1, 1, 4, 2, 1, 1, 0, 0]
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
void dailyTemperatures(vector<int>& T) {
int n = T.size();
vector<int> ans(n, 0);
stack<int> st; // 인덱스 저장
for (int i = 0; i < n; i++) {
while (!st.empty() && T[st.top()] < T[i]) {
int idx = st.top(); st.pop();
ans[idx] = i - idx;
}
st.push(i);
}
for (int x : ans) cout << x << " ";
}
int main() {
vector<int> T = {73, 74, 75, 71, 69, 72, 76, 73};
dailyTemperatures(T);
return 0;
}
আউটপুট
1 1 4 2 1 1 0 0
