leetcode题解-739-每日温度

发表于

题目

My way

最大单调递增栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) 
    {
        stack<int> s;
        vector<int> res(T.size());
        unordered_map<int, int> map;

        for (size_t i = 0; i < T.size(); ++i)
        {
            while(!s.empty() && T[s.top()] < T[i])
            {
                map[s.top()] = i - s.top();
                s.pop();
            }

            s.push(i);
        }

        while (!s.empty())
        {
            map[s.top()] = 0;
            s.pop();
        }

        for (size_t i = 0; i < res.size(); ++i)
        {
            res[i] = map[i];
        }

        return res;
    }
};

但是发现时间/空间复杂度都很低，

  • 不应该是所有的元素和右边最大(小)元素都用tuple存放在一个容器内。
  • 而应该遍历的时候就直接将结果存放起来

优化代码结构后：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) 
    {
        stack<int> s;
        vector<int> res(T.size());

        for (size_t i = 0; i < T.size(); ++i)
        {
            while(!s.empty() && T[s.top()] < T[i])
            {
                res[s.top()] = i - s.top();
                s.pop();
            }

            s.push(i);
        }


        return res;
    }
};

Reference

https://leetcode-cn.com/problems/daily-temperatures/solution/mei-ri-wen-du-by-leetcode/