Problem
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]
.
Note: The length of temperatures
will be in the range [1, 30000]
. Each temperature will be an integer in the range [30, 100]
.
Solution: Stack
Use a stack to track indices of future warmer days. From top to bottom: recent to far away.
Time complexity: O(n)
Space complexity: O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua // Running time: 148 ms class Solution { public: vector<int> dailyTemperatures(vector<int>& temperatures) { const int n = temperatures.size(); stack<int> s; vector<int> ans(n); for (int i = n - 1; i >= 0; --i) { while (!s.empty() && temperatures[s.top()] <= temperatures[i]) s.pop(); ans[i] = s.empty() ? 0 : s.top() - i; s.push(i); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment