503.Next-Greater-Element-II

503. Next Greater Element II

题目地址

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.

代码

Approach 1: Brute Force (using Double Length Array)

class Solution {
    pulic int[] nextGreaterElements(int[] nums) {
    int[] res = new int[nums.length];
    int[] doublenums = new int[nums.length * 2];
    // arraycopy(Object source_arr, int sourcePos, Object dest_arr, int destPos, int len)
    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;
  }
}

Approach #2 Better Brute Force

class Solution {
  public int[] nextGreaterElements(int[] nums) {
    int[] res = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
      res[i] = -1;
      for (int j = 1; j < nums.length; j++) {
        if (nums[(i + j) % nums.length] > nums[i]) {
          res[i] = nums[(i + j) % nums.length];
          break;
        }
      }
    }

    return res;
  }
}

Approach #3 Using Stack

单调递减栈可以找到左起第一个比当前数字大的元素

class Solution {
  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;
  }
}