496/503. 下一个更大元素 I/II¶
力扣链接(简单):https://leetcode.cn/problems/next-greater-element-i
力扣链接(中等):https://leetcode.cn/problems/next-greater-element-ii
496. 下一个更大元素 I¶
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:
| Text Only | |
|---|---|
示例 2:
| Text Only | |
|---|---|
提示:
1 <= nums1.length <= nums2.length <= 10000 <= nums1[i], nums2[i] <= 104nums1和nums2中所有整数 互不相同nums1中的所有整数同样出现在nums2中
进阶:你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗?
个人题解¶
题目描述并不清晰,说简单点就是在 nums1 中的元素,首先找到其在 nums2 中的对应位置,然后在该位置往后找比该元素更大的第一个元素,写入对应的结果中。
题目中提到,两个数组均为没有重复元素的数组,为了在遍历过程中,不用重复对另一个数组进行遍历,考虑使用哈希表对 value-index 映射。又因为,本题是在 nums2 中寻找更大元素,所以显然是对 nums2 进行遍历,然后判断遍历元素是否存在于 nums1 存在则将其写入结果。
503. 下一个更大元素 II¶
给定一个循环数组 nums ( nums[nums.length - 1] 的下一个元素是 nums[0] ),返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1 。
示例 1:
| Text Only | |
|---|---|
示例 2:
提示:
1 <= nums.length <= 104-109 <= nums[i] <= 109
个人题解¶
对于循环数组来说,有一种比较简单的办法就是将同一个数组拼接一次,如将 ABC 拼接为 ABCABC,这样从任意位置遍历一遍都相当于遍历了原数组中的所有元素,缺点是时间复杂度会增加 \(O(N)\),主要来源于拼接数组时的 insert 函数,另外,拼接还会产生一个空间复杂度为 \(O(2N) \sim O(N)\) 的数组。
还有一种办法就是将遍历长度扩充到循环数组长度的两倍,然后对 index 进行取模操作,即可完成循环遍历。