【LeetCode】下一个更大元素 IJava 题解

关注

发布于: 刚刚

题目描述

给你两个没有重复元素的数组 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 。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/next-greater-element-i著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

代码思路

今天的每日一题，题目简单明了，我们可以采用朴素算法求解，比较容易想到的优化思路是利用 hashMap 提升查询的效率。
在朴素解法中，我们采用 hashMap 记录每一个 nums2 值和下标位置，方便比较。
通过朴素算法，发现有很多的重复计算，因此，应该先求出 num2 的下一个更大的元素，在这个单调的区间，使用栈这种数据结构，可以提升计算的效率。代码如下：

通过代码

朴素解法

class Solution {    public int[] nextGreaterElement(int[] nums1, int[] nums2) {        int m = nums1.length;        int n = nums2.length;        Map<Integer, Integer> map = new HashMap<>();        for (int i = 0; i < n; i++) {            map.put(nums2[i], i);        }
        int[] ans = new int[m];        int j = 0;        for (int num : nums1) {            int idx = map.get(num);            if (idx + 1 < n) {                int k = idx + 1;                while (k < n && num >= nums2[k]) {                    k++;                }                if (k < n && num < nums2[k]) {                    ans[j++] = nums2[k];                } else {                    ans[j++] = -1;                }            } else {                ans[j++] = -1;            }        }
        return ans;    }}

复制代码

栈解法

class Solution {    public int[] nextGreaterElement(int[] nums1, int[] nums2) {        int m = nums1.length;        int n = nums2.length;
        Deque<Integer> stack = new ArrayDeque<>();        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {            while (!stack.isEmpty() && stack.peekLast() < nums2[i]) {                map.put(stack.removeLast(), nums2[i]);            }            stack.addLast(nums2[i]);        }
        int[] ans = new int[m];        for (int i = 0; i < m; i++) {            ans[i] = map.getOrDefault(nums1[i], -1);        }
        return ans;    }}

复制代码

总结

朴素解法的时间复杂度是 O(n * n), 空间复杂度是 O(n)
栈解法的时间复杂度是 O(n), 空间复杂度是 O(n)
坚持算法每日一题，加油！

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/5bdf2be3b261451eb9d8baded】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】下一个更大元素 IJava 题解

题目描述

代码思路

通过代码

总结

HQ数字卡

评论