# LC 496. Next Greater Element I

### [Problem link](https://leetcode.com/problems/next-greater-element-i/)

###### tags: `leedcode` `python` `c++` `easy` `Monotone Stack`

The **next greater element** of some element <code>x</code> in an array is the **first greater** element that is **to the right** of <code>x</code> in the same array.

You are given two **distinct 0-indexed** integer arrays <code>nums1</code> and <code>nums2</code>, where <code>nums1</code> is a subset of <code>nums2</code>.

For each <code>0 <= i < nums1.length</code>, find the index <code>j</code> such that <code>nums1[i] == nums2[j]</code> and determine the **next greater element** of <code>nums2[j]</code> in <code>nums2</code>. If there is no next greater element, then the answer for this query is <code>-1</code>.

Return an array <code>ans</code> of length <code>nums1.length</code> such that <code>ans[i]</code> is the **next greater element** as described above.

**Example 1:**

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

**Example 2:**

Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

**Constraints:**

- 1 <= nums1.length <= nums2.length <= 1000
- 0 <= nums1[i], nums2[i] <= 10⁴
- All integers in <code>nums1</code> and <code>nums2</code> are **unique** .
- All the integers of <code>nums1</code> also appear in <code>nums2</code>.

**Follow up:** Could you find an <code>O(nums1.length + nums2.length)</code> solution?

## Solution 1 - Monotone Stack
#### Python

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        d = dict()  # d[val] = next greater element of val in nums2.

        for n2 in nums2:
            while stack and n2 > stack[-1]:
                val = stack.pop()
                d[val] = n2
            stack.append(n2)

        res = []
        for n1 in nums1:
            if n1 in d:
                res.append(d[n1])
            else:
                res.append(-1)

        return res
        

#### C++

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int n = nums2.size();
        vector<int> st;
        unordered_map<int, int> umap;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && st.back() < nums2[i]) {
                umap[st.back()] = nums2[i];
                st.pop_back();
            }
            st.push_back(nums2[i]);
        }

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

>### Complexity
>m = nums1.length
>n = nums2.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(m + n) | O(m + n) |

## Note
sol1:
1. 先使用monotone stack處理nums2, 用dict來記錄nums2中每個element的next greater element.
2. 然後使用先前得到的dict來產生res.

p.s. 這題對我來說是medium...