###### tags: `Leetcode` `medium` `array` `stack` `python` `c++`

# 503. Next Greater Element II

## [題目連結:] https://leetcode.com/problems/next-greater-element-ii/

## 題目:
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:**

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:**

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

## 解題想法:
* 此題為給一數組，求出每個數字的下一個更大的數字

* 可以看做循環數組:
* 在遍歷數組的過程中
* 若往後遇到大的數，那就是第一個更大的，即是解
* 若往後一值遇到比當前小的數，表示找不到，即為-1
* **使用Stack紀錄**:紀錄位置
* stack需紀錄的是**位置**: 因為需要將更大的數放在對應的位置上，所以需要紀錄要置放在哪個位置，可將stack視為紀錄當前數字的，上個數字的位置
* 若遇到比stack頂端紀錄的位置之數**更小**者，將其位置加入到stack
* 若遇到比stack頂端紀錄的位置之數**更大**者，表示: **此數字為stack頂端紀錄位置之數的下一個更大的數**
* 將該val之放入res對應位置，並將stack.pop()
* 因為數組中最後一個數需接到起始位置繼續判斷，即為循環遍歷，所以**需遍歷兩次數組**即可

## Python:

class Solution(object):
    def nextGreaterElements(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res=[-1]*len(nums)
        stack=[] #存上個數的位置
        #first search
        for pos, val in enumerate(nums):
            if not stack or nums[stack[-1]]>val:
                stack.append(pos)
            else:
                while stack and nums[stack[-1]]<val:
                    #表示此prePos的next great就是val
                    prePos=stack.pop()
                    res[prePos]=val
                stack.append(pos)
        #second search
        for pos, val in enumerate(nums):
            if not stack:
                break
            while stack and nums[stack[-1]]<val:
                prePos=stack.pop()
                res[prePos]=val
        return res     

nums=[1,2,1]
result=Solution()
ans=result.nextGreaterElements(nums)
print(ans)

## C++:

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> stack;
        int n=nums.size();
        vector<int> res(n, -1);
        for (int pos=0; pos<n; pos++){
            if (stack.empty() || nums[stack.top()]>nums[pos])
                stack.push(pos);
            else{
                while (!stack.empty() && nums[stack.top()]<nums[pos]){
                    int prePos=stack.top(); stack.pop();
                    res[prePos]=nums[pos];
                }
                stack.push(pos);
            }
        }
        for (int pos=0; pos<n; pos++){
            if (stack.empty())
                break;
            while (!stack.empty() && nums[stack.top()]<nums[pos]){
                int prePos=stack.top(); stack.pop();
                res[prePos]=nums[pos];
            }
        }
        return res;
    }
};