1060. Daily Temperatures

Description

中文English

Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

1.The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100]

Have you met this question in a real interview?  

Example

Input:
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output:
[1, 1, 4, 2, 1, 1, 0, 0]

class Solution { public: /** * @param temperatures: a list of daily temperatures * @return: a list of how many days you would have to wait until a warmer temperature */ vector<int> dailyTemperatures(vector<int> &temperatures) { // Write your code here //单调栈，想出来用单调栈，但没有想出来怎么实现. //单调递减栈 //每个index对应的赋值是在pop栈时操作的。 //入栈的值可以是idex，也可以是val，看具体结果要求 //求附近第一个比当前元素大的值，或小的值都用单调栈 std::stack<int> stk; int n = temperatures.size(); vector<int> res(n, 0); for(int i = 0; i < n; i++){ while(!stk.empty() && temperatures[stk.top()] < temperatures[i]){ int tempIdx = stk.top(); res[tempIdx] = i - tempIdx; stk.pop(); } stk.push(i); } return res; } };