Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the $i^{th}$ day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]

Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]

Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]

Output: [1,1,0]

Constraints:

  • $1 \leq \text{temperatures.length} \leq 10^5$
  • $30 \leq \text{temperatures[i]} \leq 100$

题目分析

Stack

代码实现

#define x first 
#define y second 
using PII = pair <int, int>;
class Solution {
public:
    stack <PII> sk;
    vector <int> ans;
    vector<int> dailyTemperatures(vector<int>& t) {
        ans.resize(t.size());
        for(int i = 0; i < t.size(); ++i) {
            if(!sk.empty() && t[i] > sk.top().y) {
                while(!sk.empty() && sk.top().y < t[i]) {
                    auto p = sk.top(); sk.pop();
                    ans[p.x] = i - p.x;
                }
            }
            sk.push({i, t[i]});
        }
        return ans;
    }
};
分类: Stack

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status