KK's blog

每天积累多一些

0%

LeetCode 503 Next Greater Element II

Posted on Edited on Disqus:

LeetCode 503 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.

题目大意：

给定一个循环数组（末尾元素的下一个元素为起始元素），输出每一个元素的下一个更大的数字（Next Greater Number）。Next Greater Number是指位于某元素右侧，大于该元素，且距离最近的元素。如果不存在这样的元素，则输出-1。

注意：给定数组长度不超过10000。

解题思路：

最直接的思路是遍历每个元素，对每个元素，遍历它的后面所有元素。最差情况是递减数列，时间复杂度为O(n2)。
这题关于局部递增数组，所以考虑用递减栈。首先不考虑循环数组的情况，例如8,5,4,6,栈存入8,5,4，当6准备进栈时，5,4比6小，它们都出栈且它们的结果集为6。
循环数组其实只要将原数组复制一倍，按原算法处理，结果集取前n个元素即可。

  1. 栈不为空，准入栈元素逼出比其小的元素且赋予其结果。
  2. 该元素入栈。、
  3. 栈剩下元素的结果集赋值为-1

注意事项：

  1. 栈存储元素下标，结果集存储元素值。
  2. 栈剩下元素的结果集赋值为-1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def nextGreaterElements(self, nums: List[int]) -> List[int]:
	num_list = nums * 2
	result, stack = [0] * len(num_list), []
	for i in range(len(num_list)):
		while stack and num_list[i] > num_list[stack[-1]]:
			index = stack.pop()
			result[index] = num_list[i]
		stack.append(i)

	while stack:
		index = stack.pop()
		result[index] = -1
	return result[:len(nums)]

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int[] nextGreaterElements(int[] nums) {
	Stack s = new Stack();
	int[] nums2 = new int[nums.length*2];
	int[] re2 = new int[nums2.length];
	for(int i=0;i<nums2.length;i++){
		nums2[i] = nums[i%nums.length];
	}
	for(int i=0;i<nums2.length;i++){
		while(!s.isEmpty() && nums2[i]>nums2[(int)s.peek()]){
			int topIdx = (int)s.pop();
			re2[topIdx] = nums2[i];
		}
		s.add(i);
	}
	while(!s.isEmpty()){
		int topIdx = (int)s.pop();
		re2[topIdx] = -1;
	}
	int[] re = new int[nums.length];
	for(int i=0;i<nums.length;i++)
		re[i] = re2[i];
	return re;
}

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。

有人考虑用TreeMap，
2
1 3
但TreeMap不能保留顺序，如这个TreeMap可以对应两种数组,[2,1,3], [2,3,1]并非一一对应。

Follow-up:

  1. Given an integer array, print the Next Greater Number for every element.先从不循环数组考起。
    3,8,5,4,6,7 => 8,-1,6,6,7,-1
  2. 先让其写出暴力法brute force
  3. 再优化，第0个提示是考虑用一些数据结构，第一个提示为Stack。第二个提示，给定两个stack，怎么排序一个数组。如1,4,3,2.
    一个stack用于维护当前递增栈，另一个用于缓冲。过程：栈1从底到顶14，3准入，因为比4小，不能维持递增顺序，4入栈2，然后3入栈1，再把栈2所有元素入栈1。同理4,3入栈2,2入栈1。
  4. 最后如果是循环数组circular array，如果解决。
    3,8,5,4,6,7 => 8,-1,6,6,7,8
  5. 第一个层次暴力法，第二层次思路从第二个提示到联系到此题解法，Meets bar。最后能实现且解决follow-up，raise bar。
Free mock interview