leetcode weekly contest 61(739. Daily Temperatures)

1542 ワード

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].
タイトル
私たちにたくさんの天気の温度を見つけてから数日目に初めてこの日より温度が高くて埋められなかったと言っています.
ぶんせき
まず暴力のn平方の複雑さを考えて、とても書きやすくて、列挙すればいいです
次にn*lognと言えばセグメントツリーで逆さまにメンテナンスできますが、コードは複雑です
最後に線形の複雑さを単調キューで維持します(単調に減少するキュー)
まず、もしある日が前日より低ければ、彼は前の温度にとって何の役にも立たないことを知っています.すなわち、tem[i-1]>tem[i]」がi-1より小さい日数]がtem[i-1]より小さい場合、tem[i-1]はtem[i]より前に発効し、tem[i-1]より大きい場合、tem[i]も役に立たないことを知っています.
コード#コード#
class Solution {
public:
    vector dailyTemperatures(vector& temperatures) {
        vector< int >  ans ;
        if( temperatures.size() == 0 )
            return ans ;
        deque< int > dlist;
        deque< int > index ;
        ans.resize( temperatures.size() , 0 ) ;
        for( int i=0 ; i

時間複雑度O(n)は、各要素がキューから1回ずつキューに入るため
空間複雑度O(n)