leetcode 503. Next Greater Element II

た入场券 2022-06-03 00:49 156阅读 0赞

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 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.

本题题意和上一道题[leetcode 496. Next Greater Element I][] ，不过这里变成了循环数组，很简单的遍历即可解决本题

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    class Solution 
    {
    public:
        vector<int> nextGreaterElements(vector<int>& nums) 
        {
            vector<int> res(nums.size(),-1);
            for (int i = 0; i < nums.size(); i++)
            {
                int j = i;
                while (true)
                {
                    j = (j + 1) % (int)nums.size();
                    if (j == i)
                        break;
                    if (nums[j] > nums[i])
                        break;
                }
                if (j == i)
                    res[i] = -1;
                else
                    res[i] = nums[j];
            }
            return res;
        }
    };

[leetcode 496. Next Greater Element I]: http://blog.csdn.net/jackzhang_123/article/details/78789223