class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
}
};
503. 下一个更大元素 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原站题解
rust 解法, 执行用时: 3 ms, 内存消耗: 2.1 MB, 提交时间: 2024-06-24 09:08:36
impl Solution {
pub fn next_greater_elements(nums: Vec<i32>) -> Vec<i32> {
let n = nums.len();
let mut ans = vec![-1; n];
let mut st = vec![];
for i in (0..2 * n).rev() {
let x = nums[i % n];
while let Some(&top) = st.last() {
if x < top {
break;
}
// 由于 x 的出现，栈顶元素永远不会是左边元素的「下一个更大元素」
st.pop();
}
if i < n && !st.is_empty() {
ans[i] = *st.last().unwrap();
}
st.push(x);
}
ans
}
}
java 解法, 执行用时: 5 ms, 内存消耗: 44.9 MB, 提交时间: 2024-06-24 09:08:24
public class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
Arrays.fill(ans, -1);
Deque<Integer> st = new ArrayDeque<>();
for (int i = 2 * n - 1; i >= 0; i--) {
int x = nums[i % n];
while (!st.isEmpty() && x >= st.peek()) {
// 由于 x 的出现，栈顶元素永远不会是左边元素的「下一个更大元素」
st.pop();
}
if (i < n && !st.isEmpty()) {
ans[i] = st.peek();
}
st.push(x);
}
return ans;
}
}
cpp 解法, 执行用时: 13 ms, 内存消耗: 26 MB, 提交时间: 2024-06-24 09:08:12
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n, -1);
stack<int> st;
for (int i = 2 * n - 1; i >= 0; i--) {
int x = nums[i % n];
while (!st.empty() && x >= st.top()) {
// 由于 x 的出现，栈顶元素永远不会是左边元素的「下一个更大元素」
st.pop();
}
if (i < n && !st.empty()) {
ans[i] = st.top();
}
st.push(x);
}
return ans;
}
};
python3 解法, 执行用时: 116 ms, 内存消耗: 16.5 MB, 提交时间: 2022-11-27 11:09:08
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
n = len(nums)
ret = [-1] * n
stk = list()
for i in range(n * 2 - 1):
while stk and nums[stk[-1]] < nums[i % n]:
ret[stk.pop()] = nums[i % n]
stk.append(i % n)
return ret
golang 解法, 执行用时: 20 ms, 内存消耗: 6.5 MB, 提交时间: 2022-11-27 11:08:16
func nextGreaterElements(nums []int) []int {
n := len(nums)
ans := make([]int, n)
for i := range ans {
ans[i] = -1
}
stack := []int{}
for i := 0; i < n*2-1; i++ {
for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i%n] {
ans[stack[len(stack)-1]] = nums[i%n]
stack = stack[:len(stack)-1]
}
stack = append(stack, i%n)
}
return ans
}
javascript 解法, 执行用时: 88 ms, 内存消耗: 46.4 MB, 提交时间: 2022-11-27 11:08:01
/**
* @param {number[]} nums
* @return {number[]}
*/
var nextGreaterElements = function(nums) {
const n = nums.length;
const ret = new Array(n).fill(-1);
const stk = [];
for (let i = 0; i < n * 2 - 1; i++) {
while (stk.length && nums[stk[stk.length - 1]] < nums[i % n]) {
ret[stk[stk.length - 1]] = nums[i % n];
stk.pop();
}
stk.push(i % n);
}
return ret;
};