496. 下一个更大元素 I（数据结构系列）

小鱼儿 2023-10-05 20:17 4阅读 0赞

#### 496. 下一个更大元素 I ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]

## 解题思路 ##

让数组倒着入栈，并且挤出栈中比当前数要小的元素。  
我们先求出num2\[\]中从左往右所有元素的`下一个更大元素`并且把它们保存在map中，然后再寻找num1\[\]中存在的元素的val就行了。  
详细思路看书 267

## 代码 ##

class Solution {
        
        public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        
            HashMap<Integer, Integer> map = new HashMap<>();
            Deque<Integer> stack = new LinkedList<>();
    
            for (int i = nums2.length - 1; i >= 0; i--) {
        
                while (!stack.isEmpty() && stack.peek() <= nums2[i]) {
        
                     stack.pop();//注意，到这里nums2[i]就算满足条件也还没入栈
                }
                map.put(nums2[i],stack.isEmpty()?-1:stack.peek());
                stack.push(nums2[i]); // 入栈
            }
            int[] ans = new int[nums1.length];
            for (int i = 0; i < nums1.length; i++) {
        
                ans[i] = map.get(nums1[i]);
            }
            return ans;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210224130545118.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210224130551978.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70