LeetCode 496. Next Greater Element I(下一个较大的数 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:
- All elements in
nums1
andnums2
are unique. - The length of both
nums1
andnums2
would not exceed 1000.
解法一
思路
这个问题可以拆成两步,对于nums1
中的每个元素num1
:
- 在
nums2
中找到num1
的下标index
; - 在
nums2
的(index
,len(nums2)
)范围内找到第一个比num1
大的数。
对于第1步"在nums2
中找到num1
的下标index
",很容易想到用Map把值映射到下标就好了。这里因为nums2
中的元素一定是正数,所以可以直接用数组来模拟Map,就是拿空间换时间了。
第2步就很直接了,遍历就好了。
仔细观察还可以发现,如果nums1
中的某个元素大于等于nums2
中的元素最大值的话,这个元素得到的值肯定是-1,因为在nums2
中不可能找到比其更大的数了。
Python
class Solution(object):
def nextGreaterElement(self, findNums, nums):
"""
:type findNums: List[int]
:type nums: List[int]
:rtype: List[int]
"""
result = []
if not findNums:
return result
num_max = max(nums)
map = [-1] * (num_max + 1)
for index, num in enumerate(nums):
map[num] = index
for find_num in findNums:
if find_num >= num_max:
result.append(-1)
else:
current_index = map[find_num] + 1
while current_index < len(nums):
if nums[current_index] > find_num:
result.append(nums[current_index])
break
current_index += 1
if current_index == len(nums):
result.append(-1)
return result
Java
public class Solution {
public int[] nextGreaterElement(int[] findNums, int[] nums) {
if (findNums.length == 0) {
return new int[]{};
}
int numMax = -1;
for (int num : nums) {
if (num > numMax) {
numMax = num;
}
}
int[] map = new int[numMax + 1];
for (int i = 0; i < nums.length; i++) {
map[nums[i]] = i;
}
int[] result = new int[findNums.length];
for (int i = 0; i < findNums.length; i++) {
int currentNum = findNums[i];
if (currentNum > numMax) {
result[i] = -1;
} else {
int currentIndex = map[currentNum] + 1;
while (currentIndex < nums.length) {
if (nums[currentIndex] > currentNum) {
result[i] = nums[currentIndex];
break;
}
currentIndex++;
}
if (currentIndex == nums.length) {
result[i] = -1;
}
}
}
return result;
}
}
C++
class Solution {
public:
vector<int> nextGreaterElement(vector<int> &findNums, vector<int> &nums) {
vector<int> result;
if (findNums.empty()) {
return result;
}
int numMax = *max_element(nums.begin(), nums.end());
vector<int> map(numMax + 1, 0);
for (int i = 0; i < nums.size(); i++) {
map[nums[i]] = i;
}
for (int i = 0; i < findNums.size(); i++) {
int currentNum = findNums[i];
if (currentNum > numMax) {
result.push_back(-1);
} else {
int currentIndex = map[currentNum] + 1;
while (currentIndex < nums.size()) {
if (nums[currentIndex] > currentNum) {
result.push_back(nums[currentIndex]);
break;
}
currentIndex++;
}
if (currentIndex == nums.size()) {
result.push_back(-1);
}
}
}
return result;
}
};
楼主,请问这个题目直接模拟寻找Next Greater Element 的算法的时间复杂度是多少?
可以帮我看看我的code吗
和你的略有不同
谢 谢啊
ans = []
if not nums1: return ans d = {} for num in nums1: for i in range(0, len(nums2)): if num == nums2[i]: for j in range(i+1, len(nums2)): if nums2[j] > num: d[num] = nums2[j] break if num not in d: d[num] = -1 for num in nums1: ans.append(d[num]) return ans抱歉回复晚了。
我觉得时间复杂度应该是O(mn^2),这里取m=len(nums1),n=len(nums2)。首先你有对nums1的遍历,所以O(m)是跑不掉的;再看里面两层循环,其实大体上可以等价为插入排序(即外层循环不变,内层循环开始和结束索引均不确定),所以是O(n^2);综合下来就是O(mn^2)。
如有错误还请指正。