503. Next Greater Element II

circular in 496

T: O(n)

S: O(n)

create double length array, with duplicate content

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] newNums = new int[2*n];
        for (int i = 0; i < n; i++) {
            newNums[i] = nums[i];
            newNums[i+n] = nums[i];
        }
        
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < newNums.length; i++) {
            int num = newNums[i];
            
            System.out.println(stack.toString());
            while (!stack.isEmpty() && num > nums[stack.peek()]) {
                System.out.println("pop:" + stack.peek() + ", num:" + num + ", result[" + stack.peek() + "]=" + num);
                result[stack.peek()] = num;
                stack.pop();
            }
            if (i < n) {
                stack.push(i);
            }
            
        }
        
        return result;
    }
}

/*
 0 1 2 | 3 4 5
[1,2,1,1,2,1]

meet greater(curr), pop last index, set result[last index] = curr

if no, push index to stack


ex: 4 3 2 1

stack

3
2
1
0

end => all is [-1, -1, -1, -1]

*/

or just use % n

loop 2*n

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