题目描述

blablabla

样例

blablabla

算法

(单调栈 + hashmap) $O(n)$

先用一个单调递减的栈来算出每个数的下一个较大值，如果我新加进栈的元素比栈顶元素大，说明当前新加的元素就是当前栈顶元素的下一个较大值，然后把这个关系存到hashmap里面，找好下一个较大值的从栈里pop出来，把新的元素再放到栈里面。
最后，遍历nums1, 把里面每个元素的对应结果从hash表里取出来就好了。

时间复杂度分析：blablabla

C++ 代码

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
        vector<int> res(findNums.size(), -1);
        unordered_map<int, int> map;
        stack<int> ss;
        for (int& num : nums) {
            while (!ss.empty() && ss.top() < num) {
                map[ss.top()] = num;
                ss.pop();
            }
            ss.push(num);
        }
        for (int i = 0; i < findNums.size(); i++) {
            if (map.count(findNums[i])) {
                res[i] = map[findNums[i]];
            }
        }
        return res;
    }
};