496. Next Greater Element I（寻找下一个较大的数）

迷南。 2022-09-29 01:47 11阅读 0赞

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.

题目大意：给定两个整型数组，nums1是nums2的子数组，nums1和nums2中都没有重复的元素。对nums1中的每个数，寻找它在nums2中对应数字的右边的第一个比它大的数，如果不存在则为-1，将结果存放在一个数组中返回。

解题思路：

解法一：暴力解法，遍历nums1，对其中的每个数，在nums2中找到该数，然后在nums2中该数的右边找第一个较大的数。

代码如下：（13ms，beats 37.66%）

public int[] nextGreaterElement(int[] findNums, int[] nums) {
    		int findLen = findNums.length;
    		int numsLen = nums.length;
    		int i, j, k;
    		int[] res = new int[findLen];
    		for (i = 0; i < findLen; i++) {
    			for (j = 0; j < numsLen; j++) {
    				if (findNums[i] == nums[j]) {
    					for (k = j + 1; k < numsLen; k++) {
    						if (nums[k] > findNums[i]) {
    							res[i] = nums[k];
    							break;
    						}
    					}
    					if (k == numsLen)
    						res[i] = -1;
    					break;
    				}
    			}
    		}
    		return res;
    	}

解法二：首先确定nums2中每一个数和右边第一个较大数的关系。方法为维护一个栈和一个map，从尾到头遍历nums2，对于每一个数，如果栈顶元素小于该数，则栈顶元素出栈，直到找到大于该数的栈顶元素，此时将<该数，栈顶元素>放入map中，然后将该数也入栈；如果栈空了，则将<该数，-1>放入map中，同样将该数入栈。确定好这样一个关系后，就可以直接遍历nums1，对每一个元素直接在map中执行get，就可以确定nums2中下一个较大元素的值了。

代码如下：（14ms，beats 31.75%，没想到比暴力解法还慢- -）

public int[] nextGreaterElement(int[] findNums, int[] nums) {
            int findLen = findNums.length;
    		int numsLen = nums.length;
    		int[] res = new int[findLen];
    		if (findLen == 0 || numsLen == 0 || findLen > numsLen)
    			return res;
    		Map<Integer, Integer> map = new HashMap<>();
    		int[] stack = new int[numsLen];
    		int index = -1;
    		int i, j;
    		int curMax = nums[numsLen - 1];
    		map.put(curMax, -1);
    		for (i = numsLen - 1; i >= 0; i--) {
    			while (index >= 0) {
    				if (nums[i] > stack[index])
    					--index;
    				else {
    					map.put(nums[i], stack[index]);
    					stack[++index] = nums[i];
    					break;
    				}
    			}
    			if (index < 0) {
    				map.put(nums[i], -1);
    				stack[++index] = nums[i];
    			}
    		}
    		for (j = 0; j < findLen; j++) {
    			res[j] = map.get(findNums[j]);
    		}
    		return res;
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，11人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode（Stack)496. Next Greater Element I

1.问题 The next greater element of some element x in an array is the first greater elem

刺骨的言语ヽ痛彻心扉/ 2023年09月25日 20:41/ 0 赞/ 43 阅读

相关 Next Greater Element II（C++下一个更大元素 II）

（1）两个数组前后拼接（2）单调栈 class Solution { public: vector<int> nextGreaterEle

小灰灰/ 2023年01月17日 05:00/ 0 赞/ 150 阅读

相关 496. 下一个更大元素 I

> > 给你两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。 > > 请你找出 nums1 中每个元素在 nums2

野性酷女/ 2022年10月07日 00:51/ 0 赞/ 169 阅读

相关 [LeetCode] 496. Next Greater Element I 下一个较大的元素 I

You are given two arrays (without duplicates) `nums1` and `nums2 `where `nums1`’s elemen

我会带着你远行/ 2022年10月02日 12:52/ 0 赞/ 179 阅读

相关 496. Next Greater Element I（寻找下一个较大的数）

You are given two arrays (without duplicates) `nums1` and `nums2` where `nums1`’s elemen

迷南。/ 2022年09月29日 01:47/ 0 赞/ 12 阅读

相关 leetcode 496, 503, 556. Next Greater Element I, II, III | 496, 503, 556. 下一个更大元素 I,II,III（单调栈）

496. Next Greater Element I [https://leetcode.com/problems/next-greater-element-i/][h

分手后的思念是犯贱/ 2022年09月11日 07:25/ 0 赞/ 179 阅读

相关 [leetcode]: 496. Next Greater Element I

1.题目描述 You are given two arrays (without duplicates) nums1 and nums2 where nums1’s ele

古城微笑少年丶/ 2022年06月16日 00:56/ 0 赞/ 160 阅读

相关 496. Next Greater Element I

[原题链接][Link 1] 这个题做起来相对有意思一些。这是一个用于找规律的题。题目大意是，给两个数组nums1和nums2，其中`nums1`的元素均是nums2里面

我就是我/ 2022年06月03日 10:51/ 0 赞/ 151 阅读

相关 leetcode 556. Next Greater Element III 下一个字典序

Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which ha

一时失言乱红尘/ 2022年06月03日 04:12/ 0 赞/ 133 阅读

相关 leetcode 496. Next Greater Element I

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are

川长思鸟来/ 2022年06月03日 00:35/ 0 赞/ 179 阅读