hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Daily Temperatures
Problem: 739. Daily Temperatures
Problem Link: leetcode.com/problems/daily-temperatures/
Companies Asked: Facebook, Amazon, Microsoft, C3 IoT, Uber, Salesforce
Intuition:
How to understand a problem can be solved using Monotonic Stack?
It is a range of queries in an array situation
The minima/maxima elements
When an element is popped from the monotonic stack, it will never be utilized again.
Check the following link for more about Monotonic Stack: https://itnext.io/monotonic-stack-identify-pattern-3da2d491a61e
If we look closely then we can see all three properties mentioned above can be aligned with this problem.
We need to do some operations in a range of given temperature arrays.
We need to work with monotonically minimum temperatures in between two maximum temperatures.
The minimum temperatures in between will not be used for itself. Although, we need some way to keep them counted for adjacent maximum numbers.
Hence, we can solve this problem using Monotonic Stack.
Approach:
As a monotonic stack, we will initialize a stack holding three pieces of information, temperature, index, and count.
temperature = Temperature of ith day, index = ith day, count = number of days needed to get more warmth day than the current day.
For each ith temperature, if it is lesser than the top temperature of the stack or if the stack is empty, then push it to the stack.
If the current temperature is greater than the top temperature, then try to remove less temperatures until a bigger temperature is encountered on the top.
The removed temperatures are the required warmth days for the currently topped temperature.
Add this count to ans array.
If the stack is not empty by this time, add this count also with the day_count of the top temperature of the stack. Because the top temperature needs more other temperatures to get a warm day.
Return the ans array.
Time and Space Complexity:
Time Complexity: O(n)
Space Complexity: O(3∗n)
Code [C++]
class Solution {
public:
struct temp_info{
int temp, id, count;
};
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<temp_info>temp_stack;
int n = temperatures.size();
vector<int>ans(n, 0);
for(int i=0; i<n; i++){
if(temp_stack.empty()){
temp_stack.push({temperatures[i], i, 0});
}
else if(temp_stack.top().temp >= temperatures[i]){
temp_stack.push({temperatures[i], i, 0});
}
else{
int count;
while(!temp_stack.empty() && (temperatures[i] > temp_stack.top().temp)){
auto top_item = temp_stack.top();
ans[top_item.id] = top_item.count + 1;
temp_stack.pop();
if(!temp_stack.empty()){
temp_stack.top().count += ans[top_item.id];
}
}
temp_stack.push({temperatures[i], i, 0});
}
}
return ans;
}
};