day4 每日温度

不懂一点科研。

读题

给定一个整数数组 vector<int>& temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

思路

第一反应是对每个位置都向后遍历，看距离更高温度的距离；可以通过循环实现，也可以通过递归实现。这样做的话，一遍是向后遍历，一遍是对每个位置都要再遍历一次，时间复杂度应该是 O(n^2)？显然是劣质的做法。
经过搜索，发现 cpp 标准库中有个方法叫 find_if；但是它本身就是一个 for 循环，和手写循环差不多。
虽然很蠢，但代码实现起来很简单，于是我还是写了代码并提交了：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> answer;
        int size_list = temperatures.size();
        answer.resize(size_list);
        for(int i=0;i<size_list;i++){
            int num=temperatures[i];
            for(int j=i;j<size_list;j++){
                if(num<temperatures[j]){
                    answer[i]=j-i;
                    break;
                }
            }
        }
        return answer;
    }
};

提交之后通过了大部分测试例，但是在一个专门设置的全是 99 的例子里超时了，然后耍了点小花招过了测试，不过这是后话了。

---

是否有方法得知每个位置的温度排名？这样可以首先获取其排名，然后对比比它高的温度出现在它之前还是之后，即可得到“下一个更高温度是否会出现”和“下一个更高温度出现在哪里”。这样的话应该是 O(n)。
或许，我可以直接遍历一遍；然后使用一个新的数组来保存遍历时排序的结果。但是因为是要”距离下一个更高温度”，所以可以从后向前，寻找小于该温度的值，然后给 answer 赋值？

1. 设置一个变量保存“最大值”，另一个保存“最小值”；初始化 answer 数组，全部初始化为 0。使用 i 对距离计数，i 初始化为 0。
2. 开始从后向前遍历，最大值最小值初始化为当前值
   1. 指针向后移动，i 自增。
   2. 当前值是否比最大值大？
      1. 若是，赋值，并用 i 填充 answer；i 清零。
   3. 当前值是否比最小值小？
      1. 若是，赋值，并用 i 填充 answer；i 清零。

呃，不对。不应该是最大值最小值，而是任意一个出现过的值；要求当前值在遍历过的数列中找到属于自己的位置，这样才能判断到下一个最高温的距离。
或许可以用两个 vector 表示。
首先，对于第一个 vector，它将会保存历代的最小值；将最后一个温度赋值给 vector 首个元素，然后向前遍历；将比当前末尾元素小的温度值赋给 vector，作为新的尾部元素（vector 可变长，使用方法 emplace_back）；将比当前头元素大的温度值赋给 vector，作为新的头元素（使用 emplace）。
第二个 vector 将会保存历代最小值对应的位置。
那么，应该是：

1. 声明两个 vector 保存历代最小值及其位置，分别命名为 min_list 和 pos_list。
2. 使用 for 循环向前遍历，初始化历代最小值数列。
   1. 指针向后移动。
   2. 当前值是否比最大值（min_list 的首个元素）大？
      1. 若是，则插入首位
      2. Continue
   3. 当前值是否比最小值（min_list 的末尾元素）小？
      1. 若是，则查询末尾元素的位置，计算距离，写入 answer
      2. 将当前值插入末尾
      3. Continue
   4. 若介于最大最小值之间
      1. 使用二分法寻找其应当所在的位置
      2. 找到 min_list 中上一个元素（也就是刚好比当前元素大的那个）对应的 pos_list，计算距离，写入 answer
      3. Continue
3. 返回
   总感觉好像也是 O(n) ……不过先把代码写出来吧。于是有代码：

   class Solution {
   public:
       vector<int> dailyTemperatures(vector<int>& temperatures) {
           vector<int> min_list;
           vector<int> pos_list;
           vector<int> answer;
           int i = temperatures.size();
           answer.resize(i);
           i--;
           min_list.emplace_back(temperatures[i]);
           pos_list.emplace_back(i);
           for(;i>=0;i--){
               if(temperatures[i]>=min_list[0]){
                   min_list.emplace(min_list.begin(),temperatures[i]);
                   pos_list.emplace(pos_list.begin(),i);
                   if(i>pos_list[1] && temperatures[i]==min_list[0]) swap(pos_list[0], pos_list[1]);
                   continue;
               }
               if(temperatures[i]<=min_list.back()){
                   answer[i] = pos_list.back()-i;
                   min_list.emplace_back(temperatures[i]);
                   pos_list.emplace_back(i);
                   if(i<*(pos_list.end()-2) && temperatures[i]==min_list[0])
                       swap(pos_list[pos_list.size()-1], pos_list[pos_list.size()-2]);
                   continue;
               }
           }
   
           return answer;
       }
   };

   写到一半，仔细想想，确实是 O(n^2) 啊。写法又复杂，效率又低下，还不如暴力循环呢，起码写法简单。

结果

使用的小花招方法勉强还是通过了，使用了 2120 ms，100.37 MB 内存。

官方题解

不是我能做出来的题，直接看题解。

方法一：暴力

当然这个暴力不是我那种最简单的粗暴的暴力，而是比较有脑子的暴力。具体过程如下：

1. 由于温度有固定范围 30-100，因此创建并初始化数组 next，长度为 71，对应每个温度值。
2. 反向遍历温度列表
   1. 对于每个元素 temperatures[i]，在数组 next 中找到从 temperatures[i] + 1 到 100 中每个温度第一次出现的下标。
   2. 将其中的最小下标记为 warmerIndex，则 warmerIndex 为下一次温度比当天高的下标。
   3. 判断 warmerIndex 是否是无穷大，如果不是，那么则 warmerIndex - i 即为下一次温度比当天高的间隔天数。
   4. 令 next[temperatures[i]] = i。
3. 返回
   原理有点绕，大概就是相当于维护了一个一对一映射也就是哈希表（虽然呈现出来是数列），将 温度 和 最后一次出现的天数 对应。能用数列表示的理由是因为温度数值是有限的。
   我认为这和我第二次的想法类似，但是成熟太多。
   我想到的是对于一个有序排列的数列的维护，数列存储了温度，还有一个数列用来保存对应温度出现的位置。但是事实上，维护过程过于复杂；明明只要对一个数列特定位置的值进行修改，我却滥用了寻找和插入操作。
   当然究其原因还是因为我没有注意到温度的值是有范围的，属于读题不仔细。
   时间复杂度是 O(mn)，其中 m 是温度列表长度，小于 71；空间复杂度是 O(m)，只维护了一个温度列表。
   作为对比，我的暴力不是 O(mn) 而是 O(n^2)，在 m 有限而 n 无限的情况下，我个人认为 O(mn) 事实上可以被视作是 O(n)。

方法二：单调栈

又是一个没接触过的名词，虽然我知道单调和栈的含义，但我不知道二者组合的妙用。
题解言：

可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。

感觉类似上面的暴力里的温度数列，又有点类似我第一反应想到的所谓最大最小值。

正向遍历温度列表。对于温度列表中的每个元素 temperatures[i]，如果栈为空，则直接将 i 进栈，如果栈不为空，则比较栈顶元素 prevIndex 对应的温度 temperatures[prevIndex] 和当前温度 temperatures[i]，如果 temperatures[i] > temperatures[prevIndex]，则将 prevIndex 移除，并将 prevIndex 对应的等待天数赋为 i - prevIndex，重复上述操作直到栈为空或者栈顶元素对应的温度大于等于当前温度，然后将 i 进栈。

是正向遍历。解释一下正向遍历循环时的过程就是：

1. 判断栈是否为空
   1. 若栈为空，将 i 进栈
   2. 若栈不为空：
      1. 对比栈顶元素对应温度，和当前温度
         1. 若栈顶元素对应温度大
            1. 将 i 进栈
            2. 向前推进
         2. 若当前温度大
            1. 移除栈顶元素
            2. 记录对应 answer
   3. 继续，直到栈为空的时候停止循环，将 i 进栈
2. 继续

这个单调栈相当于一个可以容纳很多最小值的最小值缓存，越靠近栈顶的越小。
因为是正向遍历，所以栈里的数据都是之前经过了的数据，相当于都是在等待着自己对应的”下一个更高温度“。然后 i 判断：i 处的温度是否是之前某一位置温度的那个更高温度？
如果是的，i 处的温度就是之前那个位置的更高温度，那就移除等待着的数据，更新 answer，继续判断 i 对应温度是不是下一个栈顶元素等待的”下一个更高温度”。
如果不是，i 处的温度小于栈顶温度，i 是一个新的最小值，那就将 i 对应温度也视作是正在等待“下一个更高温度”的，然后向前推进。
官方有代码：

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

竟能如此优雅？

---

感觉有点类似双指针？一个在前（栈中的；虽然不是一个，也不是指针），一个在后（真指针）。

---

呃，我认为我大致理解了过程，我的直觉也告诉我这样更好，但是我不理解为什么这样做能更好。我需要数学证明。

收获

大脑被单调栈狠狠地鸿儒了，竟能如此优雅，但我理解不能，感觉比递归还难理解，而且难很多。
大概的收获是：

1. 不要滥用数组
2. 注意题目的有限的限制条件

我明天再好好想想这个单调栈是怎么回事。或许它是我一直惦记着，但一直说不出，只能用最大值最小值轻飘飘带过去的那块拼图。