Given a list of daily temperatures, produce a list 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 temperatures =
[73, 74, 75, 71, 69, 72, 76, 73]
your output should be
[1, 1, 4, 2, 1, 1, 0, 0].
Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].
暴力解法(復雜度為O(n^2),編譯器報超時了):
vector<int> dailyTemperatures(vector<int>& temperatures) {
int i, j;
int n = temperatures.size();
vector<int> res(n);
for (i = 0; i < n-1; i++) { //從0到n-2
for (j = i+1; j < n; j++) { //j從i之后找
if (temperatures[j] > temperatures[i]) { //找到一個就跳出
res[i] = j-i;
break;
}
}
if (j == n) res[i] = 0; //若找不到
}
res[i] = 0; //最后一位必為0
return res;
}
別人的思路(用棧,時間O(n)(近似),空間O(n)):
上面的暴力思路是用i遍歷數(shù)組,然后對每個i向后找.
現(xiàn)在思路是用i遍歷數(shù)組,然后對每個i向前(在棧里)找.已經(jīng)找到的元素直接出棧(或許這就是O(n)?),挺奇妙的.
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<int> s; //序號棧
vector<int> res(temperatures.size()); //結(jié)果,長度與temps一樣,初始元素全為0
for (int i = 0; i < temperatures.size(); i++) {
while (!s.empty() && temperatures[i] > temperatures[s.top()]) { //若找到第一個比棧頂溫度大的
res[s.top()] = i - s.top(); //i與棧頂?shù)男蛱栔? s.pop(); //出棧
}
s.push(i); //若沒找到比棧頂大的,先把i入棧,成為新棧頂
}
return res;
}
