496. Next Greater Element I

我就是我 2022-06-03 10:51 137阅读 0赞

[原题链接][Link 1]

这个题做起来相对有意思一些。这是一个用于找规律的题。

题目大意是，给两个数组nums1和nums2，其中`nums1`的元素均是nums2里面的子元素，问nums1中元素右边最大的元素是谁，如果没有则返回-1。

这个题的思路就是：

1.  把nums2拆分为若干递减再递增的列表。然后依次push到HashMap中。
2.  遍历nums1，获取HashMap中的value值

例：  
假定num2中的元素为\[1,3,4,2\] ->就可以拆分为 \[1, 3, 4\]、\[4\]、\[2\]这样的三个子序列。  
对应塞入的HashMap里面的内容就为  
(1, 4), (3, 4), (4, -1), (2, -1)。 **（注：实现的时候有所区别）**

假定num1中的元素为\[4,1,2\]，根据key值获取对应的value。对应的就是\[-1, 4, -1\]了。

/** * Created by Joe on 2017/12/18. * https://leetcode.com/problems/next-greater-element-i/description/ */
    public class P496 { 
        public int[] nextGreaterElement(int[] findNums, int[] nums) {
            Map<Integer, Integer> map = new HashMap<>(); // map from x to next greater element of x
            Stack<Integer> stack = new Stack<>();
            for (int num : nums) {
                while (!stack.isEmpty() && stack.peek() < num)
                    map.put(stack.pop(), num);
                stack.push(num);
            }
            for (int i = 0; i < findNums.length; i++)
                findNums[i] = map.getOrDefault(findNums[i], -1);
            return findNums;
        }
    }

[Link 1]: https://leetcode.com/problems/next-greater-element-i/description/

发表评论取消回复

表情：

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

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

相关阅读

相关 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 赞/ 33 阅读

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

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

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

相关 [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 赞/ 159 阅读

相关 LeetCode--496.496. 下一个更大元素 I(C++描述)

// Source : https://leetcode-cn.com/problems/next-greater-element-i/ // Date : 2021-10

柔情只为你懂/ 2022年09月15日 06:02/ 0 赞/ 174 阅读

相关 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 赞/ 162 阅读

相关 [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 赞/ 149 阅读

相关 496. Next Greater Element I

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

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

相关 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 赞/ 120 阅读

相关 leetcode 503. Next Greater Element II

Given a circular array (the next element of the last element is the first element of the

た入场券/ 2022年06月03日 00:49/ 0 赞/ 157 阅读

相关 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 赞/ 163 阅读