下一个更大元素 II
难度:
标签:
题目描述
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例 1:
输入: nums = [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2； 数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
示例 2:
输入: nums = [1,2,3,4,3] 输出: [2,3,4,-1,4]
提示:
1 <= nums.length <= 104-109 <= nums[i] <= 109
代码结果
运行时间: 256 ms, 内存: 16.5 MB
/*
* Solution Idea with Java Streams:
* 1. Create an array of result and initialize to -1.
* 2. Use IntStream to simulate iterating twice over the array.
* 3. For each element, check if there's a larger element in the rest of the array.
* 4. Use a Stack to store indices and find the next greater element similarly to the Java solution.
*/
import java.util.Arrays;
import java.util.Stack;
import java.util.stream.IntStream;
public class NextGreaterElementStream {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Stack<Integer> stack = new Stack<>();
IntStream.range(0, 2 * n).forEach(i -> {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
result[stack.pop()] = nums[i % n];
}
if (i < n) {
stack.push(i);
}
});
return result;
}
}
解释
方法:
这个题解使用单调栈的思路来解决问题。首先将原数组复制一遍拼接到原数组后面，模拟循环数组。然后遍历拼接后的数组，对于每个元素，将栈中所有小于当前元素的元素弹出，并将当前元素作为它们的下一个更大元素。最后将当前元素的索引压入栈中。遍历结束后，取ans数组的前n个元素作为最终结果返回。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在题解中提到的单调栈是什么样的数据结构，它是如何帮助解决这个问题的？
▷🦆
为什么要将原数组复制并拼接到自己的后面来模拟循环数组，而不是直接在原数组上进行循环操作？
▷🦆
在题解的代码实现中，为什么要初始化结果数组ans的长度为2n而不是n？
▷🦆
如果数组已经是降序排列，单调栈的行为会有什么变化？
▷相关问题
下一个更大元素 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：
输入：nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出：[-1,3,-1] 解释：nums1 中每个值的下一个更大元素如下所述： - 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。 - 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。 - 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
示例 2：
输入：nums1 = [2,4], nums2 = [1,2,3,4]. 输出：[3,-1] 解释：nums1 中每个值的下一个更大元素如下所述： - 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。 - 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
提示：
1 <= nums1.length <= nums2.length <= 10000 <= nums1[i], nums2[i] <= 104nums1和nums2中所有整数 互不相同nums1中的所有整数同样出现在nums2中
进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？