代码随想录算法训练营第五十三天|单调栈的简单介绍、LeetCode739 每日温度、LeetCoe496 下一个更大元素Ⅰ

单调栈的简单介绍：

终于来到了期待的单调栈！在正式开始单调栈之前我们先介绍一下单调栈。单调栈主要解决的问题场景就是找到当前元素左(或右)边第一个比它大(或小)的元素(位置)。具体方向和大小要看具体的题目场景。那么单调栈顾名思义，需要维护栈内单调递增或单调递减(如果是找当前元素后第一个比它大的元素位置，那么用单调递增栈，如果是找当前元素后第一个比它小的元素的位置那么就用单调递减栈)。在其中，单调栈的具体作用为存放之前遍历过的元素与当前遍历的元素做对比，因此我们需要一个数据结构来盛放之前遍历过的元素。那么接下来结合题目开始我们单调栈的应用。

题1：

指路：739. 每日温度 - 力扣（LeetCode）

思路与代码：

本题可以理解为找到数组中当前元素后第一个比它大的元素的位置与本元素的位置差，没有则返回0。典型的单调栈问题。我们定义一个单调递增栈用来盛放已经遍历过的元素位置(即题目中原有的temperatures数组的元素下标)，比较当前遍历元素的值与栈顶元素值的关系，这里有三种情况应当分类讨论，其一为当前元素对应值小于栈顶元素，此时直接使当前元素入栈；其二为当前元素对应值等于栈顶元素，此时因为不符合题意(大于非等于)，因此也是将当前遍历元素入栈；其三为当前元素对应值大于栈顶元素，维护单增栈将栈顶元素弹出，当前遍历元素入栈，此时已经找到了符合条件的元素位置，定义一个answer答案数组，此时将要出栈的栈顶元素(即temperatures数组的元素下标)与将要入栈的元素差即为此时以栈顶元素为下标的原temperatures数组中该位置的元素的最近的比它大的值。此时得到下标差放入相应的answer数组即可。代码如下：

class Solution {
public:
    vector dailyTemperatures(vector& temperatures) {
    stack st;  // 定义一个栈
    vector answer(temperatures.size(), 0);  //
    st.push(0);
    for (int i = 1; i  temperatures[st.top()]) {
                answer[st.top()] = i - st.top();
                st.pop();
            }
            st.push(i);
        }
    }
    return answer;
    }
};

题2：

指路：496. 下一个更大元素 I - 力扣（LeetCode）

思路与代码：

与上一题不同的是，在数组1中的元素对应去数组2中，在数组2中找到该元素后第一个大于该元素的值返回到数组1中符合条件的值。注意，在这里定义答案数组的时候，大小应当是数组1的大小，因为要返回数组1中元素的结果值；因为是在数组2中寻找符合条件的值，所以单调栈遍历时应当在数组2中。因为这里需要在两个数组之间做对应，所以我们定义一个map映射，其中元素值为key，元素下标为value。单调栈的应用与上题相似，分三种情况讨论，这里需要注意的是当遇到符合条件的元素时，应在map中寻找这个元素，根据map找到数组2中该下标对应的值，加入答案数组，输出即可。代码如下：

class Solution {
public:
    vector nextGreaterElement(vector& nums1, vector& nums2) {
    stack st;
    int n = nums1.size();
    vector ans(n, -1);
    if (n == 0) return ans;
    // 哈希映射的目的，能够根据元素找数值
    unordered_map umap;
    for (int i = 0; i  nums2[st.top()]) {
                if (umap.count(nums2[st.top()]) > 0) {
                    // 当map中有这个元素，就根据map找到数组2中该下标对应的值
                    int index = umap[nums2[st.top()]];
                    ans[index] = nums2[i];
                }
                st.pop();
            }
            st.push(i);
        }
    }
    return ans;
    }
};