503 Next Greater Element II 下一個更大元素 II

Description:
Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. 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, output -1 for this number.

Example:

Example 1:
Input: [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.

Note:
The length of given array won't exceed 10000.

題目描述:
給定一個循環(huán)數(shù)組（最后一個元素的下一個元素是數(shù)組的第一個元素），輸出每個元素的下一個更大元素桥滨。數(shù)字 x 的下一個更大的元素是按數(shù)組遍歷順序吟税，這個數(shù)字之后的第一個比它更大的數(shù)，這意味著你應(yīng)該循環(huán)地搜索它的下一個更大的數(shù)速那。如果不存在哆键，則輸出 -1半火。

示例 :

示例 1:

輸入: [1,2,1]
輸出: [2,-1,2]
解釋: 第一個 1 的下一個更大的數(shù)是 2塞赂；
數(shù)字 2 找不到下一個更大的數(shù)邑闺；
第二個 1 的下一個最大的數(shù)需要循環(huán)搜索跌前，結(jié)果也是 2。

注意:
輸入數(shù)組的長度不會超過 10000陡舅。

思路:

單調(diào)棧
單調(diào)棧中保存不升的下標
遍歷兩次數(shù)組獲取下一個更大元素
時間復(fù)雜度O(n), 空間復(fù)雜度O(n)

代碼:
C++:

class Solution 
{
public:
    vector<int> nextGreaterElements(vector<int>& nums) 
    {
        vector<int> result(nums.size(), -1);
        stack<int> s;
        for (int i = 0, n = nums.size(); i < n * 2 - 1; i++) 
        {
            while (!s.empty() and nums[i % n] > nums[s.top()]) 
            {
                result[s.top()] = nums[i % n];
                s.pop();
            }
            if (i < n) s.push(i);
        }
        return result;
    }
};

Java:

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int result[] = new int[nums.length], n = nums.length;
        Arrays.fill(result, -1);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n * 2 - 1; i++) {
            while (!stack.isEmpty() && nums[i % n] > nums[stack.peek()]) result[stack.pop()] = nums[i % n];
            if (i < n) stack.push(i);
        }
        return result;
    }
}

Python:

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        result, stack = [-1] * (n := len(nums)), []
        for i, num in enumerate((nums := nums + nums)):
            while stack and nums[stack[-1]] < num:
                result[stack.pop()] = num
            i < n and stack.append(i)
        return result