496. Next Greater Element I (easy)
題目說明
找到兩個數組 nums1 和 nums2 中元素的「下個更大元素」(Next Greater Element)。具體來說，對於每個出現在 nums1 中的元素 x，我們需要在數組 nums2 中找到一個位置，使得該位置之後的元素中第一個大於 x 的元素即為「下個更大元素」。如果不存在這樣的元素，則返回 -1。

解題
我們使用一個遞減的 Monotonic (單調) stack，stack 的 top 會是 stack 中最小。，當我們在遍歷 nums2 時，如果遇到一個比 stack.top() 還大的元素，則意味著該 stack.top()的下個更大元素已經找到了，因為我們找到了比它大的第一個元素。此時，我們將 stack pop 後，並將其與當前元素進行配對。

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        unordered_map<int, int> mp; // num: idx
        vector<int> res;
        for (int n: nums2) {
            // 小於 n  都 pop 掉，並且其 next greater 是 n
            while (!st.empty() && st.top() < n) {
                mp[st.top()] = n;
                st.pop();
            }
            st.push(n);
        }

        for (int n: nums1) {
            cout << mp[n] << endl;
            res.push_back(mp.count(n)? mp[n]:-1);
        }
        return res;
    }
};

假設輸入:
nums1 = {4, 1, 2};
nums2 = {1, 3, 4, 2};

當遍歷 nums2 時：
1 push 進 stack。
3 比 1 大，則 1 的下個更大元素是 3，並將 1 pop ，3 push stack。
4 比 3 大，則 3 的下個更大元素是 4，並將 3 pop，4 push stack。
2 比 4 小，直接入棧。
遍歷結束後，Hash map 的 mp 記錄的對應關係為：
1 -> 3
3 -> 4
因此，我們根據 nums1 中的每個元素來查找 mp，得到的結果為 [-1, 3, -1]。

時間複雜度是 O(n + m)