Sponsored
Sponsored
The monotonic stack approach is an efficient way to solve this problem by maintaining a stack to keep track of temperatures and their indices. We iterate over the temperatures, and for each temperature, we check if it is warmer than the temperature represented by the top index of the stack. If it is, we calculate the difference in indices to determine the number of days to wait for a warmer temperature.
This approach uses a stack to store indices of temperatures that are waiting for a warmer day. As we iterate through the list, for each temperature, we pop from the stack until the current temperature is not warmer than the temperature at the index stored at the top of the stack.
Time Complexity: O(n) - Each index is pushed and popped from the stack once.
Space Complexity: O(n) - Space used by the stack to store indices.
1#include <vector>
2#include <stack>
3using namespace std;
4
5vector<int> dailyTemperatures(vector<int>& temperatures) {
6 vector<int> answer(temperatures.size(), 0);
7 stack<int> s; // Stores indices
8 for (int i = 0; i < temperatures.size(); ++i) {
9 while (!s.empty() && temperatures[i] > temperatures[s.top()]) {
10 int prev_index = s.top();
11 s.pop();
12 answer[prev_index] = i - prev_index;
13 }
14 s.push(i);
15 }
16 return answer;
17}The C++ solution uses a vector to store the answer with initial values set to 0. A stack is used to keep track of indices of previous temperatures. For each temperature, we check if it can resolve any previous temperatures waiting for a warmer day using the stack and update the answer vector accordingly.
This approach traverses the temperature list backwards, efficiently discovering the number of days until encountering a warmer temperature. The main idea is to use an array to store the index of the next day for each temperature that is higher. By starting from the end and moving backwards, the solution is optimized in terms of lookups and updates.
Time Complexity: O(n * W) - Where W is the range of temperature values (bounded by a constant, thus linear in practice).
Space Complexity: O(W) - Space used by the array to store the closest warmer day's index.
1class Solution {
2 public intIn this Java solution, we use an auxiliary array 'next' to store the closest index for each possible temperature. By iterating through the temperatures from the end to the beginning, we update the 'next' array and compute the number of days to a warmer temperature for each day.