Daily Temperatures
Given a list of daily temperatures, produce a list that, for each day, tells you how many days you would have to wait until a warmer temperature. If there is no future day with a warmer temperature, the answer is 0.
Constraints:
- 1 <= temperatures.length <= 10^5
- 30 <= temperatures[i] <= 100
Examples:
Input: [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Explanation: For example, given the list of temperatures [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].
Solutions
Stack
We use a stack to keep track of the indices of the temperatures. We iterate through the list of temperatures, and for each temperature, we check if the stack is not empty and the current temperature is greater than the temperature at the top of the stack. If it is, we pop the top of the stack, calculate the difference between the current index and the popped index, and store it in the result array. We then push the current index onto the stack. Finally, we return the result array.
vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<int> result(temperatures.size(), 0);
stack<int> st;
for (int i = 0;
i < temperatures.size();
i++) {
while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
int lastIndex = st.top();
st.pop();
result[lastIndex] = i - lastIndex;
}
st.push(i);
}
return result;
}Follow-up:
What if we want to find the number of days until a colder temperature?
