## 题目描述：

LeetCode 496. Next Greater Element I

You are given two arrays (without duplicates) `nums1` and `nums2` where `nums1`’s elements are subset of `nums2`. Find all the next greater numbers for `nums1`'s elements in the corresponding places of `nums2`.

The Next Greater Number of a number x in `nums1` is the first greater number to its right in `nums2`. If it does not exist, output -1 for this number.

Example 1:

```Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number 1 in the first array, the next greater number for it in the second array is 3.
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
```

Example 2:

```Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
For number 2 in the first array, the next greater number for it in the second array is 3.
For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
```

Note:

1. All elements in `nums1` and `nums2` are unique.
2. The length of both `nums1` and `nums2` would not exceed 1000.

## 题目大意：

1. nums1与nums2中的所有元素都是唯一的。
2. nums1与nums2的元素个数不超过1000。

## 解题思路：

`时间复杂度O(n + m) 其中n为nums的长度，m为findNums的长度`

https://discuss.leetcode.com/topic/77916/java-10-lines-linear-time-complexity-o-n-with-explanation

```栈stack维护nums的递减子集，记nums的当前元素为n，栈顶元素为top

## Python代码：

``````class Solution(object):
def nextGreaterElement(self, findNums, nums):
"""
:type findNums: List[int]
:type nums: List[int]
:rtype: List[int]
"""
dmap = {}
stack = []
for n in nums:
while stack and stack[-1] < n:
dmap[stack.pop()] = n
stack.append(n)
return [dmap.get(n, -1) for n in findNums]
``````

`时间复杂度O(n * m) 其中n为nums的长度，m为findNums的长度`

## Python代码：

``````class Solution(object):
def nextGreaterElement(self, findNums, nums):
"""
:type findNums: List[int]
:type nums: List[int]
:rtype: List[int]
"""
dmap = {v : k for k, v in enumerate(nums)}
size = len(nums)
ans = []
for e, n in enumerate(findNums):
for j in range(dmap[n] + 1, size):
if nums[j] > n:
ans.append(nums[j])
break
if len(ans) <= e: ans.append(-1)
return ans
``````

Pingbacks已关闭。

1. ZSL 发布于 2017年2月7日 13:41 #

Can you explain the stack solution a little bit? I don't really get it. Thank you.

2. jello 发布于 2017年3月21日 01:38 #

isn't that for example 2, the next greater number is 3, but its index in nums2 is 2?

3. jello 发布于 2017年3月21日 01:50 #

forget it, I misread the problem