LeetCode 739. 每日温度

矫情吗；* 2023-02-17 03:47 80阅读 0赞

思路：单调栈

从前往后，维护一个单调下降的栈。当入栈元素大于栈顶元素时，说明栈顶元素已经找到下一个大于它的数了。

  1. class Solution {
  2. public:
  3.     vector<int> dailyTemperatures(vector<int>& T) {
  4.        vector<int> ans;
  5.        int n=T.size();
  6.        if(n==0) return ans;
  7.        for(int i=0;i<n;i++) ans.push_back(0);
  8.        stack<int> sta;
  9.        for(int i=0;i<n;i++)
  10.        {
  11.            if(sta.empty()||T[sta.top()]>=T[i])
  12.            {
  13.                sta.push(i);
  14.            }
  15.            else
  16.            {
  17.                while(sta.empty()==0&&T[sta.top()]<T[i])
  18.                {
  19.                    int tmp=sta.top();
  20.                    ans[tmp] = i-tmp;
  21.                    sta.pop();
  22.                }
  23.                sta.push(i);
  24.            }
  25.        }
  26.        return ans;
  27.     }
  28. };

发表评论

表情：
评论列表 （有 0 条评论，80人围观）

还没有评论，来说两句吧...

相关阅读

    相关 LeetCode739. 每日温度

    给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer\[i\] 是指对于第 i 天，下一个更高温度出现在几天后。如果气

    迷南。迷南。/ 0 赞/ 134 阅读

    相关 LeetCode 739. 每日温度

    根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。 例如，给定一个列表 tem

    我会带着你远行我会带着你远行/ 0 赞/ 77 阅读

    相关 【LeetCode 739】每日温度

    题目描述 请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

    ゝ一世哀愁。ゝ一世哀愁。/ 0 赞/ 93 阅读

    相关 LeetCode-739. 每日温度

    [739. 每日温度][739.] 根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高的天数。如果之后都不会升高，请输入 0 来代替。

    青旅半醒青旅半醒/ 0 赞/ 369 阅读