496.下一个最大元素I next-greater-element-i

问题描述

496.下一个更大元素I

解题思路

本题利用单调栈(monotone stack)来遍历nums2，并且利用unordered_map来存储nums1中元素和对应的结果。

代码

class Solution {
  public:
    vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2) {
        unordered_map<int, int> umap;
        stack<int> stk;
        for (int i = 0; i < nums1.size(); i++) {
            umap.insert({nums1[i], -1});
        }
        stk.push(0);
        for (int i = 1; i < nums2.size(); i++) {
            while (!stk.empty() && nums2[i] > nums2[stk.top()]) {
                if (umap.find(nums2[stk.top()]) != umap.end()) {
                    umap[nums2[stk.top()]] = nums2[i];
                }
                stk.pop();
            }
            stk.push(i);
        }
        vector<int> res(nums1.size(), -1);
        for (int i = 0; i < nums1.size(); i++) {
            res[i] = umap[nums1[i]];
        }
        return res;
    }
};