# 496 - Next Greater Element I

解法一 - Hash Table + stack

這題是筆者跟朋友模擬面試被問到的題目，所以很有感覺，一開始最直覺的想法就是先走過 nums1 的每一個 element，然後對每個 element 都去 nums2 搜尋並找到 next greater element，時間複雜度是 O(mn)，空間複雜度是 O(1)。

但這題其實可以用更高效率 - O(m+n) 的方式解掉，主要的方法就在於 nums2 搜尋 next greater element 的方法，舉例來說：

nums2 = [6,2,1,5,4]

我們可以看到，5 同時是 2 跟 1 的 next greater element，所以有一種我們會先儲存 2, 1，直到看到 5 才一次處理這兩個的 next greater element 的感覺。

而要做到這種處理，就很容易聯想到 stack，因為 stack 可以依序儲存看到的 element，然後從最新放入的開始處理。

所以，基本概念就是，只要還沒遇到更大的 element，我們就把它放進 stack，直到遇到比 stack.top() 更大的，就可以把 stack 依序 pop 出來，並更新答案。

如果已經走完 nums2，但還留在 stack 中，我們就知道這些 element 沒有 next greater element。

另外因為要 output 的答案是要 follow nums1 的 index，所以我們需要先用一個 Hash Table 來儲存 nums1 的 <value, idx> pair。

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        // Use a hash table to store the <value, idx>
        unordered_map<int, int> table;
        for(int i = 0; i < nums1.size(); ++i) {
            table[ nums1[i] ] = i;
        }

        // Use a stack to get next greater element efficiently
        vector<int> ans(nums1.size(), -1);
        stack<int> st;
        for(int i = 0; i < nums2.size(); ++i) {
            while( !st.empty() and st.top() < nums2[i] ) {
                int cur = st.top(); 
                st.pop();
                if(table.count(cur)) {
                    ans[ table[cur]] = nums2[i]; 
                }
            }    
            st.push(nums2[i]);
        }

        return ans;
    }
};