739. Daily Temperatures
題目描述
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].
Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].
解題思路
簡單的說，這道題需要我們找到某個(gè)數(shù)組元素后面的最早出現(xiàn)的元素。簡單的思路就是：從這個(gè)點(diǎn)出發(fā)鹏浅，找后面的所有點(diǎn)桨啃，是否有比它還要大的元素；如果出現(xiàn)了惠奸，就記錄下二者下標(biāo)的差值；若沒有，則記錄下0私痹。這是一種可取的思路，假設(shè)平均在后面的第k個(gè)點(diǎn)才找到符合要求的值统刮，那么這個(gè)算法的復(fù)雜度將會(huì)是O(N * K)紊遵。k的大小取決于數(shù)據(jù)，如果這是一個(gè)從大到小排列的序列侥蒙，那么K = n/2暗膜。復(fù)雜度將會(huì)是O(n^2)的規(guī)模。而題目給出的數(shù)組大小會(huì)達(dá)到30000鞭衩，很顯然学搜，這種方法是不可取的。
在上述的方法中论衍，對(duì)每一個(gè)點(diǎn)瑞佩，我們都遍歷了太多不符合要求的點(diǎn)。最好的情況是坯台，對(duì)于每一個(gè)點(diǎn)炬丸，我們只需要知道它自己的值以及第一個(gè)符合要求的值即可，那么我們要如何實(shí)現(xiàn)呢捂人？考慮用一個(gè)棧結(jié)構(gòu)來存儲(chǔ)這個(gè)列表御雕。對(duì)于每一個(gè)元素矢沿，我們在進(jìn)棧之前，先判斷棧頂元素是否比它要小酸纲，若比它要小捣鲸，則棧頂元素最早出現(xiàn)的比它自身大的元素就是當(dāng)前的元素，出棧并繼續(xù)判斷闽坡；若棧頂元素不比它小栽惶，則進(jìn)棧。這樣一來疾嗅，每一個(gè)元素我們最多只會(huì)對(duì)它進(jìn)行一次入棧和出棧的操作外厂，這樣一來，復(fù)雜度就會(huì)由O(N * K)下降到O(2n)代承。而付出的代價(jià)是汁蝶，多維護(hù)了一個(gè)棧空間论悴。
時(shí)間復(fù)雜度分析
對(duì)于每一個(gè)元素而言掖棉，最多只進(jìn)行一次入棧和出棧的操作，復(fù)雜度為O(n)膀估。
空間復(fù)雜度分析
能夠存下n個(gè)元素的棧以及返回的結(jié)果幔亥，復(fù)雜度為O(n)。
源碼
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
stack<int> Tstack;
map<int, int> next;
for (int i = 0; i < T.size(); ++i) {
if (Tstack.empty()) {
Tstack.push(i);
} else {
while (!Tstack.empty()) {
int topIndex = Tstack.top();
if (T[i] > T[topIndex]) {
Tstack.pop();
next[topIndex] = i - topIndex;
} else {
break;
}
}
Tstack.push(i);
}
}
while (!Tstack.empty()) {
next[Tstack.top()] = 0;
Tstack.pop();
}
vector<int> result;
for (int i = 0; i < T.size(); ++i) {
result.push_back(next[i]);
}
return result;
}
};
