503.下一个更大元素II
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例 1:
- 输入: [1,2,1]
- 输出: [2,-1,2]
- 解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数；第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
提示:
- 1 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
《代码随想录》算法视频公开课：单调栈，成环了可怎么办？LeetCode：503.下一个更大元素II，相信结合视频在看本篇题解，更有助于大家对本题的理解。
思路
做本题之前建议先做739. 每日温度 和 496.下一个更大元素 I。
这道题和739. 每日温度也几乎如出一辙。
不过，本题要循环数组了。
关于单调栈的讲解我在题解739. 每日温度中已经详细讲解了。
本篇我侧重与说一说，如何处理循环数组。
相信不少同学看到这道题，就想那我直接把两个数组拼接在一起，然后使用单调栈求下一个最大值不就行了！
确实可以！
将两个nums数组拼接在一起，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集即result数组resize到原数组大小就可以了。
代码如下：
// 版本一
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
// 拼接一个新的nums
vector<int> nums1(nums.begin(), nums.end());
nums.insert(nums.end(), nums1.begin(), nums1.end());
// 用新的nums大小来初始化result
vector<int> result(nums.size(), -1);
if (nums.size() == 0) return result;
// 开始单调栈
stack<int> st;
st.push(0);
for (int i = 1; i < nums.size(); i++) {
if (nums[i] < nums[st.top()]) st.push(i);
else if (nums[i] == nums[st.top()]) st.push(i);
else {
while (!st.empty() && nums[i] > nums[st.top()]) {
result[st.top()] = nums[i];
st.pop();
}
st.push(i);
}
}
// 最后再把结果集即result数组resize到原数组大小
result.resize(nums.size() / 2);
return result;
}
};
这种写法确实比较直观，但做了很多无用操作，例如修改了nums数组，而且最后还要把result数组resize回去。
resize倒是不费时间，是O(1)的操作，但扩充nums数组相当于多了一个O(n)的操作。
其实也可以不扩充nums，而是在遍历的过程中模拟走了两边nums。
代码如下：
// 版本二
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> result(nums.size(), -1);
if (nums.size() == 0) return result;
stack<int> st;
st.push(0);
for (int i = 1; i < nums.size() * 2; i++) {
// 模拟遍历两边nums，注意一下都是用i % nums.size()来操作
if (nums[i % nums.size()] < nums[st.top()]) st.push(i % nums.size());
else if (nums[i % nums.size()] == nums[st.top()]) st.push(i % nums.size());
else {
while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
result[st.top()] = nums[i % nums.size()];
st.pop();
}
st.push(i % nums.size());
}
}
return result;
}
};
可以版本二不仅代码精简了，也比版本一少做了无用功！
最后在给出 单调栈的精简版本，即三种情况都做了合并的操作。
// 版本二
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> result(nums.size(), -1);
if (nums.size() == 0) return result;
stack<int> st;
for (int i = 0; i < nums.size() * 2; i++) {
// 模拟遍历两边nums，注意一下都是用i % nums.size()来操作
while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
result[st.top()] = nums[i % nums.size()];
st.pop();
}
st.push(i % nums.size());
}
return result;
}
};
其他语言版本
Java:
class Solution {
public int[] nextGreaterElements(int[] nums) {
//边界判断
if(nums == null || nums.length <= 1) {
return new int[]{-1};
}
int size = nums.length;
int[] result = new int[size];//存放结果
Arrays.fill(result,-1);//默认全部初始化为-1
Stack<Integer> st= new Stack<>();//栈中存放的是nums中的元素下标
for(int i = 0; i < 2*size; i++) {
while(!st.empty() && nums[i % size] > nums[st.peek()]) {
result[st.peek()] = nums[i % size];//更新result
st.pop();//弹出栈顶
}
st.push(i % size);
}
return result;
}
}
Python:
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
dp = [-1] * len(nums)
stack = []
for i in range(len(nums)*2):
while(len(stack) != 0 and nums[i%len(nums)] > nums[stack[-1]]):
dp[stack[-1]] = nums[i%len(nums)]
stack.pop()
stack.append(i%len(nums))
return dp
Go:
func nextGreaterElements(nums []int) []int {
length := len(nums)
result := make([]int,length)
for i:=0;i<len(result);i++{
result[i] = -1
}
//单调递减，存储数组下标索引
stack := make([]int,0)
for i:=0;i<length*2;i++{
for len(stack)>0&&nums[i%length]>nums[stack[len(stack)-1]]{
index := stack[len(stack)-1]
stack = stack[:len(stack)-1] // pop
result[index] = nums[i%length]
}
stack = append(stack,i%length)
}
return result
}
JavaScript:
/**
* @param {number[]} nums
* @return {number[]}
*/
var nextGreaterElements = function (nums) {
const len = nums.length;
let stack = [];
let res = Array(len).fill(-1);
for (let i = 0; i < len * 2; i++) {
while (
stack.length &&
nums[i % len] > nums[stack[stack.length - 1]]
) {
const index = stack.pop();
res[index] = nums[i % len];
}
stack.push(i % len);
}
return res;
};
TypeScript：
function nextGreaterElements(nums: number[]): number[] {
const length: number = nums.length;
const stack: number[] = [];
stack.push(0);
const resArr: number[] = new Array(length).fill(-1);
for (let i = 1; i < length * 2; i++) {
const index = i % length;
let top = stack[stack.length - 1];
while (stack.length > 0 && nums[top] < nums[index]) {
resArr[top] = nums[index];
stack.pop();
top = stack[stack.length - 1];
}
if (i < length) {
stack.push(i);
}
}
return resArr;
};
Rust:
impl Solution {
pub fn next_greater_elements(nums: Vec<i32>) -> Vec<i32> {
let mut ans = vec![-1; nums.len() * 2];
let mut stack = vec![];
let double = nums.repeat(2);
for (idx, &i) in double.iter().enumerate() {
while !stack.is_empty() && double[*stack.last().unwrap()] < i {
let pos = stack.pop().unwrap();
ans[pos] = i;
}
stack.push(idx);
}
ans.into_iter().take(nums.len()).collect()
}
}
版本二：
impl Solution {
pub fn next_greater_elements(nums: Vec<i32>) -> Vec<i32> {
let (mut stack, mut res) = (vec![], vec![-1; nums.len()]);
for i in 0..nums.len() * 2 {
while let Some(&top) = stack.last() {
if nums[i % nums.len()] <= nums[top] {
break;
}
let saved_index = stack.pop().unwrap();
res[saved_index] = nums[i % nums.len()];
}
stack.push(i % nums.len());
}
res
}
}