One brush 142 monotone stack next larger element II (m)

 subject ：
 Given a circular array （ The next element of the last element is the first element of the array ）, Output the next larger element of each element .
 Numbers  x  The next larger element of is in array traversal order , The first larger number after this number ,
 This means that you should cycle through it to the next larger number . If it doesn't exist , The output  -1.
-------------
 Example ：
 Input : [1,2,1]
 Output : [2,-1,2]
 explain :  first  1  The next larger number of is  2;
 Numbers  2  Can't find the next larger number ; 
 the second  1  The next largest number of need to loop search , The result is also  2.
 Be careful :  The length of the input array will not exceed  10000.
---------------
 reflection ：
 This question and 739.  The daily temperature is almost the same .

 At different times, this problem needs to cycle through the array .

 I'm explaining the monotone stack 739.  Daily temperature   It's explained in detail in .

 This article focuses on , How to deal with circular arrays .

 I believe many students see this problem , Just like that, I directly splice the two arrays together , Then use the monotone stack to find the next maximum ！
 It can ！
 Talk about two nums Arrays are spliced together , Use the monotone stack to calculate the next maximum value of each element ,
 Finally, the result set is result Array resize To the size of the original array .

 The code is as follows ：
//  Version of a 
class Solution {
    
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
    
        //  Splice a new nums
        vector<int> nums1(nums.begin(), nums.end());
        nums.insert(nums.end(), nums1.begin(), nums1.end());
        //  With the new nums Size to initialize result
        vector<int> result(nums.size(), -1);
        if (nums.size() == 0) return result;

        //  Start monotonous stack 
        stack<int> st;
        for (int i = 0; i < nums.size(); i++) {
    
            while (!st.empty() && nums[i] > nums[st.top()]) {
    
                result[st.top()] = nums[i];
                st.pop();
            }
            st.push(i);
        }
        //  Finally, the result set is result Array resize To the original array size 
        result.resize(nums.size() / 2);
        return result;
    }
};
 This kind of writing is really intuitive , But I did a lot of useless operations , For example, modified nums Array , And finally, I have to result Array resize Go back .

resize It doesn't take time , yes $O(1)$ The operation of , But expand nums The array is equivalent to one more $O(n)$ The operation of .

 In fact, it can also be expanded nums, But in the process of traversal, the simulation goes on both sides nums.

 The code is as follows ：

//  Version 2 
class Solution {
    
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
    
        vector<int> result(nums.size(), -1);
        if (nums.size() == 0) return result;
        stack<int> st;
        for (int i = 0; i < nums.size() * 2; i++) {
    
            //  Simulate traversal on both sides nums, Note that they all use i % nums.size() To operate 
            while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
    
                result[st.top()] = nums[i % nums.size()];
                st.pop();
            }
            st.push(i % nums.size());
        }
        return result;
    }
};
 Yes, version 2 not only simplifies the code , It also did less useless work than version 1 ！
------------------------
 Code ：
class Solution {
    
	public int[] nextGreaterElements(int[] nums) {
    
		// Boundary judgment 
		if (nums == null || nums.length <= 1) return new int []{
    -1};
		int size = nums.length;
		int[] result = new int[size];// Store results 
		Arrays.fill(result, -1);// initialization 
		Stack<Integer> stack = new Stack<>();// What's on the stack is nums Element subscript in 
		for (int i = 0; i < 2 * size; i++) {
    
			while (!stack.isEmpty() && nums[i % size] > nums[stack.peek()]) {
    
				result[stack.peek()] = nums[i % size]; // to update result
				stack.pop();// Pop up the top of the stack 
			}
			stack.push(i % size);
		}
		return result;
	}
}

LC