LeetCode_单调栈_简单_496.下一个更大元素 I

不念不忘少年蓝@ 2023-10-07 20:05 51阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

nums1 中数字 x 的 下一个更大元素是指 x 在 nums2 中对应位置右侧的第一个 比 x 大的元素。

给你两个**没有重复元素**的数组 nums1 和 nums2 ，下标从 0 开始计数，**其中 nums1 是 nums2 的子集**。

对于每个 0 <= i < nums1.length ，找出满足 nums1\[i\] == nums2\[j\] 的下标 j ，并且在 nums2 确定 nums2\[j\] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans\[i\] 是如上所述的 下一个更大元素 。

**示例 1：**  
输入：nums1 = \[4,1,2\], nums2 = \[1,3,4,2\].  
输出：\[-1,3,-1\]  
解释：nums1 中每个值的下一个更大元素如下所述：

*  4 ，用加粗斜体标识，nums2 = \[1,3,**4**,2\]。不存在下一个更大元素，所以答案是 -1 。
 *  1 ，用加粗斜体标识，nums2 = \[**1**,3,4,2\]。下一个更大元素是 3 。
 *  2 ，用加粗斜体标识，nums2 = \[1,3,4,**2**\]。不存在下一个更大元素，所以答案是 -1 。

**示例 2：**  
输入：nums1 = \[2,4\], nums2 = \[1,2,3,4\].  
输出：\[3,-1\]  
解释：nums1 中每个值的下一个更大元素如下所述：

*  2 ，用加粗斜体标识，nums2 = \[1,**2**,3,4\]。下一个更大元素是 3 。
 *  4 ，用加粗斜体标识，nums2 = \[1,2,3,**4**\]。不存在下一个更大元素，所以答案是 -1 。

**提示：**  
1 <= nums1.length <= nums2.length <= 1000  
0 <= nums1\[i\], nums2\[i\] <= 104  
nums1和nums2中所有整数 互不相同  
nums1 中的所有整数同样出现在 nums2 中

**进阶**：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/next-greater-element-i  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 2.思路 ##

（1）哈希表  
① 使用 hashMap 保存数组 nums 中的元素以及对应的下标，用长度为 nums1.len 的数组 res 保存最终结果，并使用 len1、len2 分别表示数组 nums1、nums2 的长度；  
② 遍历数组 nums1，对于当前元素 nums1\[i\]，在 hashMap 中找到其对应的下标 index，然后进行如下判断：  
1）如果 index + 1 >= len2，那么说明一定不存在下一个更大元素，直接令 res\[i\] = -1；  
2）如果 index + 1 < len2，那么则遍历 nums2\[index + 1…len2\]，然后再进行相应的判断即可。

（2）哈希表 & 单调栈  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————哈希表
    class Solution {
        
        public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        
        	int len1 = nums1.length;
            int len2 = nums2.length;
            // hashMap 保存数组 nums2 中的元素以及对应的下标
            Map<Integer, Integer> hashMap = new HashMap<>();
            for (int i = 0; i < len2; i++) {
        
                hashMap.put(nums2[i], i);
            }
            int[] res = new int[len1];
            for (int i = 0; i < len1; i++) {
        
            	// nums1 是 nums2 的子集，故 hashMap 的键中一定包含 nums1[i]
                int index = hashMap.get(nums1[i]);
                if (index + 1 >= len2) {
        
                    //不存在下一个更大元素
                    res[i] = -1;
                } else {
        
                    boolean flag = false;
                    while (index + 1 < len2) {
        
                        index++;
                        if (nums2[index] > nums1[i]) {
        
                            res[i] = nums2[index];
                            flag = true;
                            break;
                        }
                    }
                    if (!flag) {
        
                    	//不存在下一个更大元素
                        res[i] = -1;
                    }
                }
            }
            return res;
        }
    }

//思路2————哈希表 & 单调栈
    class Solution {
        
        public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        
            // hashMap 保存数组 nums2 中的元素以及其对应位置右侧的第一个比 x 大的元素
            Map<Integer, Integer> hashMap = new HashMap<>();
            //单调栈，从栈底到栈顶元素单调递减
            Stack<Integer> stack = new Stack<>();
            int len1 = nums1.length;
            int len2 = nums2.length;
            //从后往前遍历数组 nums2
            for (int i = len2 - 1; i >= 0; i--) {
        
                int num = nums2[i];
                //保证栈顶元素是当前元素 num 的右侧第一个比自身大的元素
                while (!stack.isEmpty() && num >= stack.peek()) {
        
                    stack.pop();
                }
                if (stack.isEmpty()) {
        
                    //栈为空则说明 num 右侧不存在比其大的元素
                    hashMap.put(num, -1);
                } else {
        
                    hashMap.put(num, stack.peek());
                }
                stack.push(num);
            }
            int[] res = new int[len1];
            for (int i = 0; i < len1; i++) {
        
                res[i] = hashMap.get(nums1[i]);
            }
            return res;
        }
    }

[Link 1]: https://leetcode.cn/problems/next-greater-element-i/solution/xia-yi-ge-geng-da-yuan-su-i-by-leetcode-bfcoj/