題目
請根據(jù)每日氣溫列表榆俺，重新生成一個列表骑歹。對應位置的輸出為：要想觀測到更高的氣溫预烙，至少需要等待的天數(shù)。如果氣溫在這之后都不會升高道媚，請在該位置用0來代替扁掸。
例如翘县，給定一個列表temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的輸出應該是[1, 1, 4, 2, 1, 1, 0, 0]谴分。
提示:
-
氣溫列表長度的范圍是[1, 30000]锈麸。每個氣溫的值的均為華氏度，都是在[30, 100]范圍內(nèi)的整數(shù)牺蹄。
題目分析
單調(diào)棧
維護一個儲存元素下標的單調(diào)棧s忘伞，遍歷原數(shù)組，遍歷過程中對單調(diào)棧進行如下操作：
- 如果
s為空沙兰，則插入當前數(shù)組元素下標氓奈； - 如果
T[s.top()] >= T[i]，則插入當前數(shù)組元素下標僧凰； - 如果
T[s.top()] < T[i]探颈，則在res[s.top()]處插入i - s.top()，彈出s.top()训措。
遍歷過程
for (int i = 0; i < T.size(); i++) {
while ( !s.empty() && T[s.top()] < T[i] ) {
res[s.top()] = i - s.top();
s.pop();
}
s.push(i);
}
題目解答
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
// 儲存坐標
stack<int> s;
vector<int> res(T.size(), 0);
for (int i = 0; i < T.size(); i++) {
while ( !s.empty() && T[s.top()] < T[i] ) {
res[s.top()] = i - s.top();
s.pop();
}
s.push(i);
}
return res;
}
};
