LeetCode:496.下一个更大的元素

题目：

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

方法：单调栈和哈希表

单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。单调栈用途不太广泛，只处理一种典型的问题，叫做 Next Greater Element。

首先，讲解 Next Greater Number 的原始问题：给你一个数组，返回一个等长的数组，对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。不好用语言解释清楚，直接上一个例子：

给你一个数组 [2,1,2,4,3]，你返回数组 [4,2,4,-1,-1]。

解释：第一个 2 后面比 2 大的数是 4; 1 后面比 1 大的数是 2；第二个 2 后面比 2 大的数是 4; 4 后面没有比 4 大的数，填 -1；3 后面没有比 3 大的数，填 -1。

这道题的暴力解法很好想到，就是对每个元素后面都进行扫描，找到第一个更大的元素就行了。但是暴力解法的时间复杂度是 O(n^2)。

这个问题可以这样抽象思考：把数组的元素想象成并列站立的人，元素大小想象成人的身高。这些人面对你站成一列，如何求元素「2」的 Next Greater Number 呢？很简单，如果能够看到元素「2」，那么他后面可见的第一个人就是「2」的 Next Greater Number，因为比「2」小的元素身高不够，都被「2」挡住了，第一个露出来的就是答案。

vector<int> nextGreaterElement(vector<int>& nums) {
    vector<int> ans(nums.size()); // 存放答案的数组
    stack<int> s;
    for (int i = nums.size() - 1; i >= 0; i--) { // 倒着往栈里放
        while (!s.empty() && s.top() <= nums[i]) { // 判定个子高矮
            s.pop(); // 矮个起开，反正也被挡着了。。。
        }
        ans[i] = s.empty() ? -1 : s.top(); // 这个元素身后的第一个高个
        s.push(nums[i]); // 进队，接受之后的身高判定吧！
    }
    return ans;
}

为了更好地解决改题目，方便nums1找到对应地结果，可以将原本的vector存储改为用哈希表存储，nusm2数组处理后，创建nums1.size()长度的vector，for循环遍历，进行答案存储。

答题代码：

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> ans; // 存放答案的hash表
        stack<int> s;
        for (int i = nums2.size() - 1; i >= 0; i--) { // 倒着往栈里放
            while (!s.empty() && s.top() <= nums2[i]) { // 判定个子高矮
                s.pop(); // 矮个起开，反正也被挡着了。。。
            }
            // 这个元素身后的第一个高个
            ans[nums2[i]] = s.empty() ? -1 : s.top(); 
            s.push(nums2[i]); // 进队，接受之后的身高判定吧！
        }
        vector<int> m(nums1.size());
        for (int i = 0; i < nums1.size(); ++i) {
            m[i] = ans[nums1[i]];
        }
        return m;
    }
};