Leetcode 739. Daily Temperatures (cpp)_综合

题目

在这里插入图片描述

解法：

这道题关键在于两点：

对于某个降序的子序列，碰到的第一个升序的元素将会决定前面部分降序子序列位置的答案
利用stack来维持这种降序
详细解释见注释

class Solution {
    
public:vector<int> dailyTemperatures(vector<int>& T) {
    // basic idea: iterate through the array, for every element, we go back and see which // of the positions are determine by the current element. And to do so, we need to// maintain the elements in stack always as decreasing order// pair of number and indexstack<pair<int,int>> st;// initialize answersvector<int> ans(T.size(),0);int curr_ele,prev_ele,prev_ind;for(int curr_ind=0;curr_ind<T.size();curr_ind++){
    curr_ele = T[curr_ind];// pop out all the elements that are smaller than the current element,// because the answer of these elements can be determined alreadywhile(!st.empty() && st.top().first < curr_ele){
    prev_ele = st.top().first;prev_ind = st.top().second;st.pop();// answer for prev_ind is just the difference of curr_ind and prev_indans[prev_ind] = curr_ind - prev_ind;}// push the current element, the stack will still be decreasing orderst.push({
    curr_ele,curr_ind});}return ans;}
};