LeetCode101: 496. Next Greater Element I

class Solution {
public:
	vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
		// Mono-descreasing and reverse order travel.
		// The next greater of the popped value is the top of the stack, if it has any.
		//
		//  For example: [1,3,4,2]
		// the stack goes:
		// [2]
		// [4] -> 2
		// [4, 3, 1]
		stack<int> st;

		vector<int> res;
		unordered_map<int, int> m;

		for (int i = nums2.size() - 1; i >= 0; i--) {
			while (!st.empty() && st.top() < nums2[i]) {
				int c = st.top();
				st.pop();
				if (!st.empty()) {
					m[c] = st.top();
				}
			}
			st.push(nums2[i]);
		}

		while (st.size() > 1) {
			int c = st.top();
			st.pop();
			m[c] = st.top();
		}

		for (int i = 0; i < nums1.size(); i++) {
			if (m.find(nums1[i]) != m.end()) {
				res.push_back(m[nums1[i]]);
			} else {
				res.push_back(-1);
			}
		}
		return res;
	}
};


/*
[1,3,5,2,4]
[6,5,4,3,2,1,7]

The stack goes:

[7, 1]
[7, 2] -> 1 and 1 is next greater is the top of the stack
*/