# 503 - Next Greater Element II

解法一 - stack 儲存 pair

因爲這題會有 duplicate number，所以我們不能再用 Hash Table 來儲存 value 跟 index pair，而是要把 idx 資訊也直接放到 stack 中。

另外一個要處理的東西就是 circular，而最多其實只需要走 nums 兩次，就可以處理完畢。實作如下：

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        // Use a stack to get next greater element efficiently
        vector<int> ans(nums.size(), -1);
        stack< pair<int, int> > st;
        for(int i = 0; i < 2*nums.size(); ++i) {
            int idx = i % nums.size();

            while( !st.empty() and st.top().first < nums[idx] ) {
                pair<int, int> cur = st.top(); 
                st.pop();
                if(ans[cur.second] == -1) {
                    ans[cur.second]  = nums[idx]; 
                }
            }   

            if(ans[idx] == -1) {
                st.push( make_pair(nums[idx], idx) );
            }
        }

        return ans;
    }
};