Next Greater Element II


  • 1

    Click here to see the full article post


  • 1

    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;
        }

  • 0
    This post is deleted!

  • 0
    S

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


  • 0
    S

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


  • 0
    S

    As I knew, in CPU "%" as nextE=nums[j%nums.length] of this question is slower than "+" or "-" as nextE=nums[j<nums.length?j:j-nums.length] of this question.


  • 1
        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
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.