LeetCode 503 - Next Greater Element II

Next Greater Element

LeetCode 496 - Next Greater Element I
LeetCode 503 - Next Greater Element II
LeetCode 556 - Next Greater Element III
https://leetcode.com/problems/next-greater-element-ii/

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.

X.
https://leetcode.com/articles/next-greater-element-ii/

  public int[] nextGreaterElements(int[] nums) {

    int[] res = new int[nums.length];

    Stack<Integer> stack = new Stack<>();

    for (int i = 2 * nums.length - 1; i >= 0; --i) {

      while (!stack.empty() && nums[stack.peek()] <= nums[i % nums.length]) {

        stack.pop();

      }

      res[i % nums.length] = stack.empty() ? -1 : nums[stack.peek()];

      stack.push(i % nums.length);

    }

    return res;

  }

http://blog.csdn.net/u014688145/article/details/70254955
这道题和上面本质上是一样的，也可以在O(n)内完成，它是一个循环找peek问题，但没关系，复制一份同样的数组，放在它的后面就好了。
这个for循环过程含义更加清楚，num表示当前我所在的位置，而stack记录的就是之前我所走过的状态。
public int[] nextGreaterElements(int[] nums) { int len = nums.length; int[] ans = new int[len]; Arrays.fill(ans, -1); Stack<Integer> stack = new Stack<>(); for (int i = 0; i < 2 * len; i++){ int num = nums[i % len]; while(!stack.isEmpty() && nums[stack.peek()] < num) ans[stack.pop()] = num; if (i < len) stack.push(i); } return ans; }
https://leetcode.com/problems/next-greater-element-ii/discuss/98273/java-10-lines-and-c-12-lines-linear-time-complexity-on-with-explanation

The only difference here is that we use stack to keep the indexes of the decreasing subsequence

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

https://discuss.leetcode.com/topic/77881/typical-ways-to-solve-circular-array-problems-java-solution

The first typical way to solve circular array problems is to extend the original array to twice length, 2nd half has the same element as first half. Then everything become simple.

The second way is to use a stack to facilitate the look up. First we put all indexes into the stack, smaller index on the top. Then we start from end of the array look for the first element (index) in the stack which is greater than the current one. That one is guaranteed to be the Next Greater Element. Then put the current element (index) into the stack.

    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        
        Stack<Integer> stack = new Stack<>();
        for (int i = n - 1; i >= 0; i--) {
            stack.push(i);
        }
        
        for (int i = n - 1; i >= 0; i--) {
            result[i] = -1;
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
                stack.pop();
            }
            if (!stack.isEmpty()){
                result[i] = nums[stack.peek()];
            }
            stack.add(i);
        }
        
        return result;
    }

X.
https://discuss.leetcode.com/topic/77871/short-ac-solution-and-fast-dp-solution-45ms

public int[] nextGreaterElements2(int[] nums) {
 int  n = nums.length;
 int[] res = new int[n];
 for (int i = 0; i < n; i++) {
  res[i] = -1;
  for (int k = i+1; k < i + n; k++) {
   if (nums[k%n] > nums[i]){
    res[i] = nums[k%n];
    break;
   }
  }
 }
 return res;
}

https://discuss.leetcode.com/topic/77881/typical-ways-to-solve-circular-array-problems-java-solution

    public int[] nextGreaterElements(int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            max = Math.max(max, num);
        }
        
        int n = nums.length;
        int[] result = new int[n];
        int[] temp = new int[n * 2];
        
        for (int i = 0; i < n * 2; i++) {
            temp[i] = nums[i % n];
        }
        
        for (int i = 0; i < n; i++) {
            result[i] = -1;
            if (nums[i] == max) continue;
            
            for (int j = i + 1; j < n * 2; j++) {
                if (temp[j] > nums[i]) {
                    result[i] = temp[j];
                    break;
                }
            }
        }
        
        return result;
    }

X. https://leetcode.com/articles/next-greater-element-ii/

  public int[] nextGreaterElements(int[] nums) {

    int[] res = new int[nums.length];

    int[] doublenums = new int[nums.length * 2];

    System.arraycopy(nums, 0, doublenums, 0, nums.length);

    System.arraycopy(nums, 0, doublenums, nums.length, nums.length);

    for (int i = 0; i < nums.length; i++) {

      res[i] = -1;

      for (int j = i + 1; j < doublenums.length; j++) {

        if (doublenums[j] > doublenums[i]) {

          res[i] = doublenums[j];

          break;

        }

      }

    }

    return res;

  }