当前位置：首页 > article >正文

力扣 739. 每日温度【经典单调栈题目】

article 2024/11/13 15:10:12

1. 题目

在这里插入图片描述

理解题意：
1.1. 给一个温度集合，要返回一个对应长度的结果集合，这个结果集合里面的元素 i 是当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差，若是当前元素不存在下一个更高温度的元素，则这个位置用0代替；

2. 思路

本题用单调栈来求解；
单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素；【单调栈：让栈中的元素保持单调递增或者递减】
简单的说，单调栈的作用就是存放遍历过的元素！
3.1. 可以将单调栈看成一种缓存机制，只存《以后》要用到的元素！
3.2 简单说：我们在遍历的时候遍历到当前的元素，我们并不清楚之前都遍历过哪些元素了，那么不知道之前遍历过哪些元素，那就不知道这个元素有没有可能比之前的某个元素大？这个元素有没有可能是之前某一个元素右边第一个比前面某个元素大的元素呢？所以需要一个数据结构来记录我们之前遍历过的元素！
3.3 本题单调栈的作用就是：记录遍历过的元素然后和当前遍历到的元素做一个对比，看是不是《所谓下一个更大！！！》
思考一下，有三种情况：【这一题栈存放的是下标而不是元素，所以要做个映射，要这样表示：T[i] 与 T[st.top()]；】【T[i] 是当前遍历到的元素， T[st.top] 栈顶下标对应的温度】
4.1. 当前遍历的元素 > 栈口（top）元素;
4.2. 当前遍历的元素 = 栈口（top）元素;
4.3. 当前遍历的元素 < 栈口（top）元素;
做个模拟：【可以自己试一下】【:index】，以T:[73, 74, 75, 71, 69, 69, 72, 76, 73] 为例子；【单调栈：记录我们之前遍历过的元素！】
1. 先将 73【0】入栈，接着遍历下一个元素， 74【1】，而74【1】 > 73【0】，则更新result 数组， result[st.top() = 0] = 1 - 0 = 1【当前遍历的元素的下标 - 栈顶元素（栈存放的是温度 Temperature 元素的下标，理解好映射关系）】，此时就记录好一个结果了！【即下标 0 的位置的元素找到了右边第一个比它大的元素的是谁，二者的距离是多少！】既然 index = 0 的结果已经记录下来了，就没有必要在单调栈中再存放这个下标0了；【虽然单调栈中是存放遍历过的元素，但是遍历过的元素若结果已经计算完了，就没有必要存放了！】所以，这里应该是将73【0】弹出单调栈中，再将 74【1】push到单调栈中；【这样就保证了单调栈是单调递增的！】
2. 接着往下遍历到 75【2】，75【2】 > 74【1】（当前st.top() 栈顶元素是 74 【1】），那结果同上面一样，并且更新result数组， result[st.top() = 1] = 2 - 1 = 1，更新单调栈：当前栈顶元素为 75【2】；
3. 接着往下遍历到71【3】，这里它没有比当前栈顶的元素大了，那就没有记录结果的必要了，因为要找的是在75【2】右边比 75 这个元素大的元素的位置；那就直接把71【3】push 到栈中，作为【之后】遍历过的元素来使用，那么当前单调栈的栈顶元素为 71【3】，当前单调栈示意图：
  3.1.
  3.2 可以看出在单调栈中，我们保证了元素的单调递增，正是因为保证了栈中元素是单调递增的，才会做到找到的元素是栈顶元素的右边第一个比它大的元素！【再做一个对应的映射计算！】
4. 接着往下遍历到69【4】，同上面同理，当前单调栈示意图如下：
  4.1.
5. 接着往下遍历到69【5】，这里要注意了！！！当前遍历元素和栈顶元素相同了，首先不做记录结果的过程，依然将69【5】直接加入到单调栈中，因为我们要求的是这个元素右边比它大的元素，而不是大于等于的元素；当前单调栈的示意图如下：【什么时候出栈？单调栈记录的是什么？当当前遍历的元素比栈顶元素大的时候才出栈，认为找到了此元素右边第一个比之大的元素 i】
  5.1.
6. 接着往下遍历到 72【6】，发现72【6】 > 当前栈顶 top 元素69【5】，所以要做记录结果的更新【说明72【6】是 69【5】右边第一个更大的元素】， result[st.top() = 5] = 6(72[6]) - 5 = 1；那么就将当前栈顶元素69【5】弹出， 72【6】继续与当前栈顶元素69【4】比较，发现：72【6】 > 69【4】，即栈顶元素 69【4】右边第一个更大元素是72【6】，此时要做一个记录结果的更新， result[st.top() = 4] = 6(72[6]) - 4 = 2；接着再比较，同上面两个同理，更新result[st.top() = 3] = 6 - 3 = 3；（71【3】右边第一个比他大的元素是72【6】）那就接着弹出71【3】，然后比较当前栈顶元素75【2】和 72【6】， 72 < 75，将72【6】入栈即可；
  6.1. 到了这一步应该会明确一点了！！！：单调栈 === 存放已经遍历过的但是还没有找到比自己大的元素！！！
7. 接着遍历到76【7】，按照前面的逻辑更新result数组：result[st.top() = 6] = 7 - 6 = 1，更新后将 st.top()【72(6)】弹出，继续比较，发现76【7】 > 75【2】，记录更新结果 result[st.top() = 2] = 7 - 2 = 5，更新后将 st.top()【75(2)】弹出；接着栈空就把76【7】加入栈中；
  7.1.
8. 接着遍历到 73【8】，同样进行逻辑比较， 73 < 76，直接加入单调栈中，当前栈中示意图如下：
  8.1.
9. 至此整个 temperature 数组遍历结束，这时候发现下标7 和 8 一直在单调栈中没有弹出来，说明这两个元素右边没有比它更大的元素了；这里有个巧妙的做法：初始化 result 数组为 0，这样有需要更新的就会附上值，不需要更新的说明没有更大元素，那默认就是 0 值了！

3. 代码

以上的模拟可以自己进行一遍，直接见代码注释

/**
    完整的做法
**/

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        // 定义一个栈
        stack<int> stk; // 实现单调栈
        // 定义一个结果数组
        int len = temperatures.size();
        vector<int> res(len, 0);    // 要返回的结果数组
        // 首先题目中提到 temperature 的长度是 >= 1的
        stk.push(0);    // 第一个下标 0
        for(int i = 1; i < len; ++i){
            // 进循环开始遍历数组
            // 单调栈中存储 下标
            while (!stk.empty() && temperatures[i] > temperatures[stk.top()]){
                // 若栈不为空 并且 当前遍历的元素大于了 当前栈顶元素， 则需要更新result
                res[stk.top()] = i - stk.top();
                // 并且要把单调栈更新， 保持栈内元素单调递增
                stk.pop();
            }
            // 将当前元素推到栈中
            stk.push(i);
        }
        // 若栈不为空， 但是遍历结束了， 说明这个时候栈内元素对应的温度往后面是没有更大温度了
        // 这一步可以不写 | 因为 vector<int> res(len, 0);
        while (!stk.empty()){
            res[stk.top()] = 0;
            // 并且要把单调栈更新， 保持栈内元素单调递增
            stk.pop();
        }
        return res;

    }
};