• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

739. Daily Temperatures

开发技术 开发技术 5小时前 4次浏览

原题链接

739. Daily Temperatures

题目描述

请根据每日气温列表temperatures ,请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高,请在该位置用 0 来代替。

示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]

问题分析

实际上这道题应该使用递减栈 Descending Stack (栈底到栈顶递减)来做,栈里只有递减元素。

思路是这样的,我们遍历数组,如果栈不空,且当前数字大于栈顶元素,那么如果直接入栈的话就不是递减栈了,所以我们取出栈顶元素,那么由于当前数字大于栈顶元素的数字,而且一定是第一个大于栈顶元素的数,那么我们直接求出下标差就是二者的距离了,然后继续看新的栈顶元素,直到当前数字小于等于栈顶元素停止,然后将数字入栈,这样就可以一直保持递减栈,且每个数字和第一个大于它的数的距离也可以算出来了。

代码

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res(n, 0);
        stack<int> s;
        
        for(int i = 0; i < n; i++){
            while(!s.empty() && temperatures[i] > temperatures[s.top()]){
                int top = s.top(); s.pop();
                res[top] = i - top;
            }
            s.push(i);
        }

        return res;
    }
};

程序员灯塔
转载请注明原文链接:739. Daily Temperatures
喜欢 (0)