Stacks and Queues Monotonic stack
210. Next Greater Element I
You are given an array of distinct integers nums and an array queries. Every value in queries also
appears in nums, and no value appears twice in queries.
For each query, find its value in nums and look at the values after it. The answer for that query is the
first of those values that is larger than the query, or -1 if none of them is larger.
Return an array answer of the same length as queries, where answer[i] is the answer for queries[i].
Example 1
Input: nums = [6, 2, 4, 1, 3, 8, 5], queries = [4, 6, 1, 5]
[8,8,3,-1]Explanation: After 4 come 1 and 3, which are smaller, and then 8. The first larger value after 6 is also 8, and 1 is followed straight away by the larger 3. Nothing comes after 5, so its answer is −1.
Example 2
Input: nums = [9, 6, 3, 0], queries = [6, 0, 9]
[-1,-1,-1]Explanation: Every value of nums is smaller than the one before it, so no query has a larger value after it.
Example 3
Input: nums = [8, 1, 5], queries = [5, 1]
[-1,5]Explanation: Nothing comes after 5. The 8 is larger than 5, but it comes before 5, so it does not count. The first value after 1 is 5, which is larger.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 1051 ≤ queries.length ≤ nums.length0 ≤ nums[i], queries[i] ≤ 109- All the values of
numsare distinct. - All the values of
queriesare distinct, and each of them appears innums.
Clarifying questions
What you would ask an interviewer before writing any code.