LeetCode

LeetCode-739 每日温度

nkul · 7月11日 · 2020年 323次已读

反着看,从右往左开始找,符合单调栈的套路(从已遍历的数组中找最近的大于或者小于的数)。

class Solution {
public:
    vector dailyTemperatures(vector& T) {
        //从数组最右边开始找,找最近比它大的数下标!!!
        int size = T.size();
        vector res(size,0);
        int stk[size],tt=-1;//模拟栈,保存的是下标
        for(int i=size-1;i>=0;i--){
            while(tt>=0 && T[stk[tt]]<=T[i]) tt--;
            if(tt>=0) res[i] = (stk[tt]-i);
            else res[i] = 0;
            stk[++tt] = i;
        }
        return res;
    }
};


0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!