力扣第739题题解

思路

我的第一个思路，是利用两个栈和一个哈希表。第一个栈存放数组数据，第二个栈存放数组下标。使用for循环遍历的时候，如果栈为空或者栈顶元素大于等于要放进去的元素，则放进去；否则，依次pop两个栈，同时，将当前元素下标与存放数组下标的栈顶元素相减，即为需要等待的天数。使用map来存放。
但是这里存在一个问题。如果数组元素存在相同的元素，则后遍历的数组元素“需要等待的天数”在map里面会覆盖前遍历的相同元素。

于是，我放弃了一个栈。只留下一个栈，存放下标。同时，map的key值从元素的值，改为元素在原来数组的下标：避免了相同元素覆盖值的问题。

代码

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& t) {
        stack<int> b;
        vector<int> c(t.size(),0);
        for(int i=0;i<t.size();i++){
            if(b.empty()){
                //a.push(t[i]);
                b.push(i);//栈空则push
            }
            else {
                if(t[b.top()]>=t[i]){
                    //a.push(t[i]);
                    b.push(i);//栈顶小于当前元素则push
                }
                else {
                    while(!b.empty()&&t[b.top()]<t[i]){
                        //int tmp=a.top();
                        //a.pop();
                        int tmp=b.top();
                        b.pop();
                        c[tmp]=i-tmp;
                    }//栈可能存在一连串比当前元素要小的元素
                    //a.push(t[i]);
                    b.push(i);//记得要在栈为空或者栈顶大于当前元素之后，push这个元素
                    

                }
            }
        }
        while(!b.empty()){
            c[b.top()]=0;
            b.pop();
        }//此时栈还存留的元素，没有下一个更小的值了，全部赋值为0
        return c;
    }
};