• 今日分享一下做的题目，力扣739. 每日温度，496. 下一个更大元素 I

前面有很多题目都没有记录，下次二刷的时候会再把有意思的题目记录一下。

今天主要学习的是单调栈的应用，单调栈的应用解决的问题就是寻找数组中某个元素往前或往后的元素中遇到的第一个最大或最小的元素。

其主要作用是以某种形式来存放遍历过的元素，以便与接下来遍历的元素比较得出结果。

739每日温度 题目描述：

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

示例：

输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]

暴力解法（超时）： 很自然想到的就是两层for循环，遍历当前元素往后的元素找到第一个比本身大的元素

for (int i = 0; i < temperatures.size(); i++){
            int temp = 0;
            for (int j = i + 1; j < temperatures.size(); j++){
                if (temperatures[j] > temperatures[i]){
                    temp = j;
                    break;
                }

但是是很不幸，如果遇到满屏的相同元素的数组，示例47这种究极极端情况时，就只能请超级计算机帮忙了。

单调栈： 具体的想法就是先将首个元素放入栈中，再将遍历的元素T[1]与栈顶的元素比较，如果T[1]小于栈顶元素的话（即T[1] < T[0]），就把T[1]元素存入栈中，此时从栈顶到栈底就形成了单调递增的单调栈

再遍历T[2]，如果T[2]等于栈顶元素的话（即T[2] == T[1]），也把T[2]放入栈中，因为题目要求的是大于本身元素。

再遍历T[3]，此时T[3]大于栈顶元素的话（即T[3] > T[2]）， 就说明T[3]是T[2]往后遇到的第一个比自身大的元素，用results数组记录后弹出栈顶元素

此时的栈顶元素就变为了T[1]，再比较T[3]与T[1]的大小，此时T[3]大于T[1]说明T[3]是T[1]往后遇到的第一个比自身大的元素，同样操作后弹出T[1] 此时栈顶元素变为了T[0]，

如果T[3]>T[0]，即T[3]也是T[0]往后遇到的第一个比自身大的元素，同样也是result数组记录后弹出，此时栈为空了，再将T[3]放入栈中，等待往后遍历的元素来与栈顶元素进行比较，以得出T[3]位置的结果

如果T[3]<T[0]，即T[3]并非T[0]往后遇到的第一个比自身大的元素，而是另有其人。则可将T[3]放入栈中作为栈顶元素等待与后续元素进行比较。

如果知道遍历完数组都为未找到目标元素，结果即应为0，可在初始化result数组是就全部值初始化为0。 此流程可由以下代码得出：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<int> st;
        vector<int> result(T.size(), 0);
        st.push(0);
        for (int i = 1; i < T.size(); i++) {
            if (T[i] < T[st.top()]) {
                st.push(i);
            } else if (T[i] == T[st.top()]) {
                st.push(i);
            } else {
                while (!st.empty() && T[i] > T[st.top()]) {
                    result[st.top()] = i - st.top();
                    st.pop();
                }
                st.push(i);
            }
        }
        return result;
    }
};

代码中由于result数组需要记录的是自身到下一个比自身大的元素的距离（即下标相减），在元素放入单调栈时就可直接放入数组下标以方便result数组记录。

496 下一个更大的元素I 题目描述：

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

示例：

输入：nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出：[-1,3,-1] 解释：nums1 中每个值的下一个更大元素如下所述： – 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。 – 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。 – 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

本题在力扣网站上标注为简单题，大概是因为能用暴力法直接解出，但是如果用单调栈解法的话，却是比上一题还要麻烦一些。 具体的思路还是和上题一样，区别就是需要给nums1数组与nums2数组做一下映射，可以使用哈希表map。

unordered_map<int, int> umap;
for (int i = 0; i < nums1.size(); i++) {
    umap[nums1[i]] = i;
}

以元素本身为key，而以下标作为value，因为nums1是nums2的子集且无重复元素，所以map一定可以映射到nums2数组。 剩下的操作就与上一题没有太大的区别了，不过还有一些需要注意的地方。

for (int i = 1; i < nums2.size(); i++) {
            while (!st.empty() && nums2[i] > nums2[st.top()]) {
                if (umap.count(nums2[st.top()]) > 0) { 
                    int index = umap[nums2[st.top()]];
                    result[index] = nums2[i];
                }
                st.pop();
            }
            st.push(i);
        }

今日推荐歌曲（点击网站左下角即可收听，倒数第二首）：フレンドリー ——sakanaction。