Dare2Solve
The problem requires us to determine how many days one must wait until a warmer temperature occurs for each day in a list of daily temperatures. If there is no future day with a warmer temperature, the output for that day should be 0
.
A brute-force solution would involve checking for each day how many days it takes until a warmer day is found. However, this would be inefficient due to its high time complexity. A more efficient approach involves using a stack to keep track of indices of days that haven't found a warmer day yet. By iterating through the list of temperatures and comparing the current temperature with those on the stack, we can find the correct waiting days more efficiently.
Initialization: Create a list result
initialized to 0 with the same length as temperatures
. Also, initialize an empty stack to keep track of pairs of temperatures and their indices.
Iterate through temperatures: For each temperature in the list, do the following:
result
list at the popped index.Return the result: The result
list will now contain the number of days required to encounter a warmer temperature for each day.
O(n)
, where n
is the number of days in the list. Each element is pushed and popped from the stack at most once, leading to a linear time complexity.
O(n)
due to the space required for the result
list and the stack.
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<int> result(temperatures.size(), 0);
stack<pair<int, int>> stack; // stores pair of (temperature, index)
for (int i = 0; i < temperatures.size(); ++i) {
int temp = temperatures[i];
while (!stack.empty() && temp > stack.top().first) {
auto [t, index] = stack.top();
stack.pop();
result[index] = i - index;
}
stack.push({temp, i});
}
return result;
}
};
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
result = [0] * len(temperatures)
stack = [] # stores pair of (temperature, index)
for i, temp in enumerate(temperatures):
while stack and temp > stack[-1][0]:
pop = stack.pop()
result[pop[1]] = i - pop[1]
stack.append((temp, i))
return result
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] result = new int[temperatures.length];
Stack<int[]> stack = new Stack<>(); // stores pair of (temperature, index)
for (int i = 0; i < temperatures.length; i++) {
int temp = temperatures[i];
while (!stack.isEmpty() && temp > stack.peek()[0]) {
int[] pop = stack.pop();
result[pop[1]] = i - pop[1];
}
stack.push(new int[]{temp, i});
}
return result;
}
}
var dailyTemperatures = function(temperatures) {
result = Array(temperatures.length).fill(0)
stack = []
for (const [i, temp] of temperatures.entries()) {
while (stack.length > 0 && temp > stack.at(-1)[0]) {
pop = stack.pop()
result[pop[1]] = i-pop[1]
}
stack.push([temp, i])
}
return result
};