Next Greater Element II


I think first adding all element indices to stack is easier to understand for me.
It means for the right most side elements, first trying to find next greater element from left beginning. The same time adding right elements to stack for elements on its left.public int[] nextGreaterElements(int[] nums) { int n = nums.length; Stack<Integer> stack = new Stack(); for(int i = n  1; i >= 0; i){ stack.push(i); } int[] res = new int[n]; for(int i = n  1; i >= 0; i){ res[i] = 1; while(!stack.isEmpty() && nums[stack.peek()] <= nums[i]){ stack.pop(); } if(!stack.isEmpty()) res[i] = nums[stack.peek()]; stack.push(i); } return res; }

@Jerry Your approach looks like the Approach #2 Better Brute Force in some ways.

@vinod23 Your said "Approach #3 Using Stack"s Time complexity is O(n). But I think the while is also like for loop to compare one by one, find and pick up the next Greater Element. So its Time complexity is also O(n*n) as worst.

def nextGreaterElements(self, nums): """ :type nums: List[int] :rtype: List[int] """ stack, res, n = [], [1]*len(nums), len(nums) for i in xrange(0, 2*n): while stack and nums[i%n] > nums[stack[1]]: top = stack.pop() if res[top] == 1: res[top] = nums[i%n] stack.append(i%n) return res