62-每日温度

自己的做法

算法思想

使用单调栈，栈中存放温度及相应的索引，从栈底到栈顶，温度依次递减。

栈中的元素代表都还没有找到下一个更高的温度。

遍历数组：

1. 如果栈为空，则直接进栈
2. 如果栈不为空，则比较栈顶元素和当前温度大小
   • 如果当前温度更大，循环弹栈，直到当前温度小于等于栈顶元素温度。并添加到哈希表，key为索引，值为等待的天数。即当前温度的索引 - 栈顶元素的索引。
   • 如果当前温度小于栈顶元素，则直接入栈

遍历完后，将所有还在栈中的元素也添加到哈希表中，value为0，即没有找到更高的温度。

然后根据索引从哈希表中依次添加到结果列表res中。

算法实现

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        //第一个是索引，第二个是温度
        stack<pair<int, int>> s;
        unordered_map<int, int> map;
        for(int i = 0; i < temperatures.size(); i++) {
            if(s.empty() || temperatures[i] <= s.top().second) {
                s.push({i, temperatures[i]});
            } else {
                while (!s.empty() && temperatures[i] > s.top().second) {
                    map.insert({s.top().first, i - s.top().first});
                    s.pop();
                }
                s.push({i, temperatures[i]});
            }
        }
        while (!s.empty()) {
            map.insert({s.top().first, 0});
            s.pop();
        }
        vector<int> res;
        for(int i = 0; i < temperatures.size(); i++) {
            res.push_back(map[i]);
        }
        return res;
    }
};

性能分析

时间复杂度：遍历一遍列表，又依次访问一遍哈希表，为$O(n)$。n为列表长度。

空间复杂度：一个栈，一个哈希表。$O(n)$。

参考解法

算法思想

还是使用单调栈，思想差不多。但是比我那个要简单，我那个做法想复杂了。

栈中只放索引，不需要放对应温度。也不需要哈希表。可以提前申请好结果列表res的内存，res的大小和给定的温度列表大小是相同的。

然后根据索引去比较温度。

申请内存后，元素初始为0。所以可以只需修改那些能够观测到更高温度的对应元素，无法观测到更高温度的，就应该是0。

算法实现

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> s;
        int n = temperatures.size();
        vector<int> res(n);
        for(int i = 0; i < n; i++) {
            while (!s.empty() && temperatures[i] > temperatures[s.top()]) {
                int preIndex = s.top();
                res[preIndex] = i - preIndex;
                s.pop();
            }
            s.push(i);
        }

        return res;
    }
};

性能分析

时间复杂度：$O(n)$。

空间复杂度：$O(n)$。

另一个解法

算法思想

留个坑。

算法实现

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res(n);
        for(int i = n - 2; i >= 0; i--) {
            for(int j = i + 1; j < n; j += res[j]) {
                if(temperatures[i] < temperatures[j]) {
                    res[i] = j - i;
                    break;
                } else if(res[j] == 0) {
                    res[i] = 0;
                    break;
                }
            }
        }
        return res;
    }
};