【LeetCode-496】下一个更大元素 I

4.2 下一个更大元素 I【496】

4.2.1 题目描述

4.2.2 方法一：暴力

思路和算法

代码

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int m = nums1.length, n = nums2.length;int[] res = new int[m];for (int i = 0; i < m; ++i) {int j = 0;while (j < n && nums2[j] != nums1[i]) {++j;}int k = j + 1;while (k < n && nums2[k] < nums2[j]) {++k;}res[i] = k < n ? nums2[k] : -1;}return res;}
}

复杂度分析

• 时间复杂度：O(mn)，其中 m 是 nums 1 \textit{nums}_1 nums1​ 的长度，n 是 nums 2 n u m s 2 \textit{nums}_2nums2 nums2​nums2 的长度。

• 空间复杂度：O(1)。

4.2.3 方法二：单调栈 + 哈希表

思路

我们可以先预处理 nums 2 \textit{nums}_2 nums2​ ，使查询 nums 1 \textit{nums}_1 nums1​中的每个元素在 nums 2 \textit{nums}_2 nums2​中对应位置的右边的第一个更大的元素值时不需要再遍历 nums 2 \textit{nums}_2 nums2​。于是，我们将题目分解为两个子问题：

• 第 1 个子问题：如何更高效地计算 $\textit{nums}_2 $中每个元素右边的第一个更大的值；

• 第 2 个子问题：如何存储第 1 个子问题的结果。

算法

我们可以使用单调栈来解决第 1 个子问题。倒序遍历 nums 2 \textit{nums}_2 nums2​，并用单调栈中维护当前位置右边的更大的元素列表，从栈底到栈顶的元素是单调递减的。

具体地，每次我们移动到数组中一个新的位置 $i$，就将当前单调栈中所有小于 $\textit{nums}_2[i] $ 的元素弹出单调栈，当前位置右边的第一个更大的元素即为栈顶元素，如果栈为空则说明当前位置右边没有更大的元素。随后我们将位置 $i$ 的元素入栈。

因为题目规定了 nums 2 \textit{nums}_2 nums2​ 是没有重复元素的，所以我们可以使用哈希表来解决第 2 个子问题，将元素值与其右边第一个更大的元素值的对应关系存入哈希表。

细节

因为在这道题中我们只需要用到 nums 2 \textit{nums}_2 nums2​中元素的顺序而不需要用到下标，所以栈中直接存储 nums 2 \textit{nums}_2 nums2​ 中元素的值即可。

代码

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {Map<Integer, Integer> map = new HashMap<Integer, Integer>();Deque<Integer> stack = new ArrayDeque<Integer>();for (int i = nums2.length - 1; i >= 0; --i) {int num = nums2[i];while (!stack.isEmpty() && num >= stack.peek()) {stack.pop();}map.put(num, stack.isEmpty() ? -1 : stack.peek());stack.push(num);}int[] res = new int[nums1.length];for (int i = 0; i < nums1.length; ++i) {res[i] = map.get(nums1[i]);}return res;}
}

复杂度分析

• 时间复杂度：O(m + n)，其中 m 是 nums 1 \textit{nums}_1 nums1​的长度，n 是 nums 2 \textit{nums}_2 nums2​ 的长度。我们需要遍历 nums 2 \textit{nums}_2 nums2​ 以计算 nums 2 \textit{nums}_2 nums2​ 中每个元素右边的第一个更大的值；需要遍历 nums 1 \textit{nums}_1 nums1​ 以生成查询结果。

• 空间复杂度：O(n)，用于存储哈希表。

4.2.4 my answer—暴力

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int res[] = new int[nums1.length];int count = 0;int j;for(int i = 0;i<nums1.length;i++){  // 对nums1进行遍历int num1 = nums1[i];for(j = 0;j<nums2.length;j++){  // 找到数组nums2中与nums1[i]相等的数if(num1 == nums2[j] && j != nums2.length-1)break;if(j == nums2.length-1)res[count++] = -1;   // 如果是最后一个，直接为-1}for(int k = j+1;k<nums2.length;k++){    // 找nums1[i]中右边第一个比它大的数if(nums2[k]>num1){res[count++] = nums2[k];break;}if(k == nums2.length-1)res[count++] = -1;}}return res;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！