【题目描述】

对于给定的一个temperatures数组，每个元素表示当天的温度。对于每天的温度，求出下一次更高的温度出现在几天后。

【算法】单调栈

我们可以维护一个栈结构，先将数组的首元素入栈，然后开始遍历这个数组，如果遍历到的数组元素比栈顶元素小，那么就入栈；如果相等，也入栈；当遍历到的数组元素比此时栈顶的元素大时，记录此时相隔的天数，然后将栈顶元素弹出，继续比较栈顶的元素和数组元素的大小，直到栈顶元素小于或者等于栈顶元素，此时将该数组元素入栈。然后接着遍历下一个数组元素，依次循环。

由于题目中求的是相隔的天数，所以我们不需要将数组元素入栈，只需入栈该元素的下标即可，这样就可以直接计算相隔的天数：数组元素对应的下标减去栈顶元素对应的下标，就是该栈顶元素与下一个更高温度相隔的天数。

图示：（以题目中的示例1为例）

可以发现，栈中的元素（下标对应的元素）始终保持单调递减（从栈底到栈顶），因此成为单调栈。

【代码】

代码语言：javascript

AI代码解释

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n=temperatures.size();
        vector<int> ans(n,0);
        stack<int> st;//存储下标
        st.push(0);
        for(int i=1;i<n;i++)
        {
            //遇到温度大于栈顶的，就一直出栈，保持递减性
            while(!st.empty()&&temperatures[st.top()]<temperatures[i])
            {
                int index=st.top();
                st.pop();
                ans[index]=i-index;
            }
            st.push(i);
        }
        return ans;
    }
};

时间复杂度O(N)，每个元素最多入栈依次。空间复杂度O(N)

二，下一个更大的元素I

【题目描述】

本题存在两个数组，nums1是nums2的子集，对于nums1数组的每个元素，求出这些元素在对应nums2数组中的下一个更大的元素。如果不存在，则为-1

【算法】单调栈

本题与上一题的思路一样，只不过加了一点要求。

求当前元素的下一个更大的元素，就需要维护一个单调栈（单调递减）。

本题还是求数组nums2上每个元素的下一个更大的元素是多少。所以还是在nums2数组上使用单调栈。和上题的过程一样，只不过在判断的时候，还需加上一个条件。

假设找到了当前栈顶的下一个更大元素k，还需判断栈顶元素是否在nums1中出现过，如果该元素在nums1中出现过，那么就将k记录在最终结果数组ans中，不过还需要保证和nums1数组的位置一一对应。所以可以做下预处理工作，将数组nums1中的元素和下标使用哈希表保存起来。