739. Daily Temperatures
1. Description
Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.
For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].
2. Note
- The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].
3. Solutions
My Accepted Solution
n = i_temperature.size()
Time complexity: O($n^2$)
Space complexity: O(n)
// brute force
3.1 Next Array
n = i_temperature.size()
r is the range of temperature, while it is 30~70, which is constant, we could treat it as O(1)
Time complexity: O(nr)
Space complexity: O(r)
class Solution
{
public:
// vector<int> dailyTemperatures(vector<int>& T)
vector<int> dailyTemperatures(const vector<int> &i_temperature)
{
// the temperature range is 30~100, we start from 0, which is more simple than every temperature minus 30
// nextTemperature means the next index of any temperature
vector<int> nextTemperature(101, -1);
vector<int> result(i_temperature.size(), INT_MAX);
// since the question is to find the next higher temperature
// we go through them from back to front, during which we could update the nextTemperature
for(int i = i_temperature.size() - 1; i >= 0; i--)
{
nextTemperature[i_temperature[i]] = i;
for(int temperature = i_temperature[i] + 1; temperature <= 100; temperature++)
{
result[i] = min(result[i], nextTemperature[temperature] == -1 ? INT_MAX : nextTemperature[temperature] - i);
}
if(result[i] == INT_MAX) result[i] = 0;
}
return result;
}
};
3.2 Stack
n = i_temperature.size()
r is the range of temperature, while it is 30~70, which is constant, we could treat it as O(1)
Time complexity: O(nr)
Space complexity: O(r)
// we also go through the array from back to front
// we store
class Solution
{
public:
// vector<int> dailyTemperatures(vector<int>& T)
vector<int> dailyTemperatures(const vector<int> &i_temperature)
{
vector<int> result(i_temperature.size());
stack<int> higherTempIndex; // store temperature's indexs after current index, higherTempIndex.top() is the lowest temperature
for(int i = i_temperature.size() - 1; i >= 0; i--)
{
// find the next temperature, since the stack is ordered, the first valid one is the answer
while(!higherTempIndex.empty() && i_temperature[i] >= i_temperature[higherTempIndex.top()]) higherTempIndex.pop();
// when the stack is empty, we can't find any valid answer, so it is impossibleto find it
result[i] = (higherTempIndex.empty() ? 0 : higherTempIndex.top() - i);
higherTempIndex.push(i);
}
return result;
}
};