Daily Temperatures
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 ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
example
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
日別の気温として、例えば[73, 74, 75, 71, 69, 72, 76, 73]のような配列が与えられる
ある日について、次により高い気温となる日は何日後かそれぞれの日について答えよ
この場合だと答えは[1, 1, 4, 2, 1, 1, 0, 0]になる
解法
ある日の気温がそれ以前の日の気温を超えた場合
スタックの要素を全てpopしつつindexの差分(日数)を記録していけばok
時間計算量は$ O(N)
空間計算量は最悪で$ O(N)
解くのにかかった時間
25分(方針立てるのに10分、その後エラー対処に10分かけた)
code:solution.cpp
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
// pair(index, temp)
stack<pair<int, int>> st;
vector<int> ans(T.size(), 0);
for (int i=0; i<T.size(); i++) {
while (!st.empty() && st.top().second < Ti) { int idx = st.top().first;
st.pop();
}
st.push(make_pair(i, Ti)); }
return ans;
}
};
code:main.go
func dailyTemperatures(temperatures []int) []int {
n := len(temperatures)
ret := make([]int, n, n)
// index 0: index
// index 1: temperature
st := [][]int{}
for i, t := range temperatures {
for {
if top1 < t { ret[top0] = i - top0 } }
st = append(st, []int{i, t})
}
return ret
}