LeetCode: Next Greater Element II Posted on February 20, 2018July 26, 2020 by braindenny Next Greater Element II Similar Problems: LeetCode: Leetcode: Next Greater Element I CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #monotone, #circulararray 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. Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. // https://code.dennyzhang.com/next-greater-element-ii // Basic Ideas: monotone stack // // 1 3 2 1 4 // 1 3 2 1 4 1 3 2 1 4 // Complexity: Time O(n), Space O(n) func nextGreaterElements(nums []int) []int { nums2 := make([]int, len(nums)*2) for i, v := range nums { nums2[i] = v nums2[i+len(nums)] = v } // monotone stack l := make([]int, len(nums2)) stack := []int{} for i, _ := range l { l[i] = -1 } for i, v := range nums2 { for len(stack)>0 && nums2[stack[len(stack)-1]] < v { l[stack[len(stack)-1]] = v stack = stack[0:len(stack)-1] } stack = append(stack, i) } return l[0:len(nums)] } ## https://code.dennyzhang.com/next-greater-element-ii ## Basic Ideas: Descending stack ## ## Complexity: Time O(n), Space O(n) class Solution(object): def nextGreaterElements(self, nums): """ :type nums: List[int] :rtype: List[int] """ length = len(nums) stack = [] res = [None]*length for i in xrange(length*2): i = i % length # if current element is bigger, it's the target of previous undecided elements while len(stack) != 0 and nums[i] > nums[stack[-1]]: k = stack.pop() res[k] = nums[i] # No need to check if already examined if res[i] is None: stack.append(i) for i in xrange(length): if res[i] is None: res[i] = -1 return res Post Views: 7