文章講解：代碼隨想錄 (programmercarl.com)
題目鏈接：739. 每日溫度 - 力扣（LeetCode）
題目：
請(qǐng)根據(jù)每日 氣溫 列表，重新生成一個(gè)列表。對(duì)應(yīng)位置的輸出為：要想觀測(cè)到更高的氣溫，至少需要等待的天數(shù)。如果氣溫在這之后都不會(huì)升高，請(qǐng)?jiān)谠撐恢糜?0 來(lái)代替。
例如，給定一個(gè)列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的輸出應(yīng)該是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：氣溫 列表長(zhǎng)度的范圍是 [1, 30000]。每個(gè)氣溫的值的均為華氏度，都是在 [30, 100] 范圍內(nèi)的整數(shù)。
分析：
什么時(shí)候用單調(diào)棧：通常是一維數(shù)組，要尋找任一個(gè)元素的右邊或者左邊第一個(gè)比自己大或者小的元素的位置，此時(shí)我們就要想到可以用單調(diào)棧了。
單調(diào)棧里只需要存放元素的下標(biāo)i就可以了，如果需要使用對(duì)應(yīng)的元素，直接T[i]就可以獲取。
單調(diào)棧里元素是遞增呢？ 還是遞減呢？
這里我們要使用遞增循序（再?gòu)?qiáng)調(diào)一下是指從棧頭到棧底的順序），因?yàn)橹挥羞f增的時(shí)候，加入一個(gè)元素i，才知道棧頂元素在數(shù)組中右面第一個(gè)比棧頂元素大的元素是i。
接下來(lái)我們用temperatures = [73, 74, 75, 71, 71, 72, 76, 73]為例來(lái)逐步分析，輸出應(yīng)該是 [1, 1, 4, 2, 1, 1, 0, 0]。
首先先將第一個(gè)遍歷元素加入單調(diào)棧
加入T[1] = 74，因?yàn)門(mén)[1] >T[0]（當(dāng)前遍歷的元素T[i]大于棧頂元素T[st.top()]的情況），而我們要保持一個(gè)遞增單調(diào)棧（從棧頭到棧底），所以將T[0]彈出，T[1]加入，此時(shí)result數(shù)組可以記錄了，result[0] = 1，即T[0]右面第一個(gè)比T[0]大的元素是T[1]。
加入T[2]，同理，T[1]彈出
加入T[3]，T[3]< T[2] （當(dāng)前遍歷的元素T[i]小于棧頂元素T[st.top()]的情況），加T[3]加入單調(diào)棧
加入T[4]，T[4] == T[3] （當(dāng)前遍歷的元素T[i]等于棧頂元素T[st.top()]的情況），此時(shí)依然要加入棧，不用計(jì)算距離，因?yàn)槲覀円蟮氖怯颐娴谝粋€(gè)大于本元素的位置，而不是大于等于！
加入T[5]，T[5] >T[4] （當(dāng)前遍歷的元素T[i]大于棧頂元素T[st.top()]的情況），將T[4]彈出，同時(shí)計(jì)算距離，更新result
T[4]彈出之后， T[5] >T[3] （當(dāng)前遍歷的元素T[i]大于棧頂元素T[st.top()]的情況），將T[3]繼續(xù)彈出，同時(shí)計(jì)算距離，更新result
直到發(fā)現(xiàn)T[5]小于T[st.top()]，終止彈出，將T[5]加入單調(diào)棧
加入T[6]，同理，需要將棧里的T[5]，T[2]彈出
同理，繼續(xù)彈出
此時(shí)棧里只剩下了T[6]
加入T[7]， T[7]< T[6] 直接入棧，這就是最后的情況，result數(shù)組也更新完了。
其實(shí)定義result數(shù)組的時(shí)候，就應(yīng)該直接初始化為0，如果result沒(méi)有更新，說(shuō)明這個(gè)元素右面沒(méi)有更大的了，也就是為0。
以上在圖解的時(shí)候，已經(jīng)把，這三種情況都做了詳細(xì)的分析。
重慶分公司
重慶分公司
class Solution {public:
vectordailyTemperatures(vector& temperatures) {stackst;
vectorresult(temperatures.size(), 0);
st.push(0);
for (int i = 1; i< temperatures.size(); i++) {if (temperatures[i]< temperatures[st.top()]) {st.push(i);
} else if (temperatures[i] == temperatures[st.top()]) {st.push(i);
} else {while (!st.empty() && temperatures[i] >temperatures[st.top()]) {result[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
}
return result;
}
}; 文章講解：代碼隨想錄 (programmercarl.com)
題目鏈接：496. 下一個(gè)更大元素 I - 力扣（LeetCode）
題目：
給你兩個(gè) 沒(méi)有重復(fù)元素 的數(shù)組 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
請(qǐng)你找出 nums1 中每個(gè)元素在 nums2 中的下一個(gè)比其大的值。
nums1 中數(shù)字 x 的下一個(gè)更大元素是指 x 在 nums2 中對(duì)應(yīng)位置的右邊的第一個(gè)比 x 大的元素。如果不存在，對(duì)應(yīng)位置輸出 -1 。
class Solution {public:
vectornextGreaterElement(vector& nums1, vector& nums2) {stackst;
vectorresult(nums1.size(), -1);
if (nums1.size() == 0) return result;
unordered_mapumap;
for (int i = 0; i< nums1.size(); i++) {umap[nums1[i]] = i;
}
st.push(0);
for (int i = 1; i< nums2.size(); i++) {if (nums2[i]< nums2[st.top()]) {st.push(i);
} else if (nums2[i] == nums2[st.top()]) {st.push(i);
} else {while (!st.empty() && nums2[i] >nums2[st.top()]) {if (umap.count(nums2[st.top()]) >0) {int index = umap[nums2[st.top()]];
result[index] = nums2[i];
}
st.pop();
}
st.push(i);
}
}
return result;
}
}; 你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
