503. Next Greater Element II

Posted on Edited on In

503. Next Greater Element II

Description

Difficulty: Medium

Related Topics: Array, Stack, Monotonic Stack

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, return -1 for this number.

Example 1:

1
2
3
4
5
Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2;
The number 2 can't find next greater number.
The second 1's next greater number needs to search circularly, which is also 2.

Example 2:

1
2
Input: nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]

Constraints:

  • 1 <= nums.length <= 104
  • -109 <= nums[i] <= 109

Hints/Notes

  • Monotonic Stack

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int size = nums.size();
        vector<int> res(size, 0);
        stack<int> greater;
        for (int i = size * 2 - 1; i >= 0; i--) {
            while (!greater.empty() && greater.top() <= nums[i % size]) {
                greater.pop();
            }
            res[i % size] = greater.empty() ? -1 : greater.top();
            greater.push(nums[i % size]);
        }
        return res;
    }
};