题目大意:给你一个组数A里面每个元素都不相同。再给你一个数组B,元素是A的子集,问对于B中的每个元素,在A数组中相同元素之后第一个比它的元素是多少。
Problem:
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:
1 2 3 4 5 6 |
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:
1 2 3 4 5 |
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.
Solution 1: Brute Force
Time complexity: O(n^2)
Space complexity: O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua // Running time: 13 ms class Solution { public: vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) { vector<int> ans; for (int num : findNums) { ans.push_back(-1); int index = std::find(nums.begin(), nums.end(), num) - nums.begin(); for (int i = index; i < nums.size(); ++i) if (nums[i] > num) { ans.back() = nums[i]; break; } } return ans; } }; |
Solution 2: HashTable + Brute Force
Time complexity: O(n^2)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua // Running time: 15 ms class Solution { public: vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) { unordered_map<int, int> indices; for (int i = 0 ; i < nums.size(); ++i) indices[nums[i]] = i; vector<int> ans; for (int num : findNums) { ans.push_back(-1); for (int i = indices[num]; i < nums.size(); ++i) if (nums[i] > num) { ans.back() = nums[i]; break; } } return ans; } }; |
Solution 3: Stack + HashTable
Using a stack to store the nums whose next greater isn’t found yet.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua // Running time: 11 ms class Solution { public: vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) { stack<int> s; unordered_map<int, int> next; for (int num : nums) { while (!s.empty() && num > s.top()) { next[s.top()] = num; s.pop(); } s.push(num); } vector<int> ans; for (int num : findNums) ans.push_back(next.count(num) ? next[num] : -1); return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment