739.每日温度
#栈#单调栈 2024-08-15 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> result(temperatures.size(), 0);
        stack<int> data; // 存储下标

        for (int i = 0; i < temperatures.size(); i++) {
            while (!data.empty() && temperatures[i] > temperatures[data.top()]) {   // 单调递减栈
                result[data.top()] = i - data.top();
                data.pop();
            }
            data.push(i);
        }
        return result;
    }
};

前面做的一些关于栈的题目，通常只涉及两类：

  • 一类是利用栈的对称性（20.有效的括号）
  • 另一类是利用栈的接口，这本质上是在熟悉使用栈接口的基础上再加上一些与题目相关的思路解题（155.最小栈和232.用栈实现队列）

然而，此题并不在上面之中，也是极容易被忘记的题型，即单调栈。这也是我为何给单独给此类题型一个标签，这本身属于栈这个范围，因为单调栈就是在栈的基础上保留顺序的特性，但是又因为这种题的技巧容易被遗忘（反正我是这样），必须单独拎出来强调一番。

当我们想要维持顺序，且有如下要求：

  1. 寻找数组中每个数左边第一个比它小的数，使用单调递增栈
  2. 寻找数组中每个数左边第一个比它大的数，使用单调递减栈
  3. 寻找数组中每个数右边第一个比它小的数，使用单调递增栈
  4. 寻找数组中每个数右边第一个比它大的数，使用单调递减栈

在此题中，我们要寻找数组中每个数右边第一个比它大的数，使用单调递减栈。