496. 下一个更大元素 I

Posted on Edited on In , ,
转载自Leet Code

题目描述

给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。 找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。 如果不存在，对应位置输出 -1 。

示例 1: >输入: nums1 = [4,1,2], nums2 = [1,3,4,2]. >输出:[-1,3,-1] >解释: > 对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。 > 对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。 > 对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。

示例 2: >输入: nums1 = [2,4], nums2 = [1,2,3,4]. >输出: [3,-1] >解释: > 对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。 > 对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

提示：

  • nums1和nums2中所有元素是唯一的。
  • nums1和nums2 的数组大小都不超过1000。

我的代码

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class MySolution496 
{
    public int[] nextGreaterElement(int[] nums1, int[] nums2) 
	{
    	HashMap<Integer, Integer> nums2IndexMap = new HashMap();
    	int []nums2Max = new int[nums2.length];
    	
    	int max = -1;
    	for (int i=nums2.length-1; i>=0; i--)
    	{
    		nums2IndexMap.put(nums2[i], i);
    		
			int j=i+1;
			for (; j<nums2.length; j++)
				if (nums2[j]>nums2[i])
				{
					nums2Max[i] = nums2[j];
					break;
				}
			if (j>=nums2.length) nums2Max[i] = -1;
    	}
    	
    	int []result = new int[nums1.length];
    	for (int i=0; i<nums1.length; i++)
    		result[i] = nums2Max[nums2IndexMap.get(nums1[i])];
    	return result;
    }
}

方法一: 单调栈

\(T(M,N) = O(M+N)\), \(S(N) = O(N)\)

我们可以先对 nums2 中的每一个元素，求出其下一个更大的元素。 将这些答案放入哈希映射（HashMap）中，再遍历数组 nums1，并直接找出答案。 对于 nums2，我们可以使用单调栈来解决这个问题。

我们维护了一个单调栈，栈中的元素从栈顶到栈底是单调不降的。 当我们遇到一个新的元素 nums2[i] 时，我们判断栈顶元素是否小于nums2[i]， 如果是，那么栈顶元素的下一个更大元素即为 nums2[i]，我们将栈顶元素出栈。 重复这一操作，直到栈为空或者栈顶元素大于 nums2[i]。 此时我们将 nums2[i]入栈，保持栈的单调性， 并对接下来的 nums2[i + 1], nums2[i + 2] ... 执行同样的操作。

代码

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution496 
{
	Stack<Integer> stack;
	HashMap<Integer, Integer> map;
	
    public int[] nextGreaterElement(int[] nums1, int[] nums2) 
    {
	Stack<Integer> stack;
	HashMap<Integer, Integer> map;
	
    public int[] nextGreaterElement(int[] nums1, int[] nums2) 
    {
    	stack = new Stack(); // stack: 暂时还没找到nums2里位于他们右边又大于他们的
        map = new HashMap();
    	
    	for (int i=0; i<nums2.length; i++)
    	{
			while (!stack.isEmpty()&&nums2[i]>stack.peek())
				map.put(stack.pop(), nums2[i]);
            stack.push(nums2[i]);
    	}
        while (!stack.isEmpty())
            map.put(stack.pop(), -1);
    	
    	int []ans = new int[nums1.length];
    	
    	for (int i=0; i<nums1.length; i++)
    		ans[i] = map.get(nums1[i]);
    	
    	return ans;
    }
}