mirror of
https://github.com/youngyangyang04/leetcode-master.git
synced 2026-02-02 18:39:09 +08:00
359 lines
11 KiB
Markdown
Executable File
359 lines
11 KiB
Markdown
Executable File
* [做项目（多个C++、Java、Go、测开、前端项目）](https://www.programmercarl.com/other/kstar.html)
|
||
* [刷算法（两个月高强度学算法）](https://www.programmercarl.com/xunlian/xunlianying.html)
|
||
* [背八股（40天挑战高频面试题）](https://www.programmercarl.com/xunlian/bagu.html)
|
||
|
||
# 503.下一个更大元素II
|
||
|
||
[力扣题目链接](https://leetcode.cn/problems/next-greater-element-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
|
||
|
||
## 算法公开课
|
||
|
||
**[《代码随想录》算法视频公开课](https://programmercarl.com/other/gongkaike.html)：[单调栈，成环了可怎么办？LeetCode：503.下一个更大元素II](https://www.bilibili.com/video/BV15y4y1o7Dw/)，相信结合视频在看本篇题解，更有助于大家对本题的理解**。
|
||
|
||
|
||
## 思路
|
||
|
||
做本题之前建议先做[739. 每日温度](https://programmercarl.com/0739.每日温度.html) 和 [496.下一个更大元素 I](https://programmercarl.com/0496.下一个更大元素I.html)。
|
||
|
||
这道题和[739. 每日温度](https://programmercarl.com/0739.每日温度.html)也几乎如出一辙。
|
||
|
||
不过，本题要循环数组了。
|
||
|
||
关于单调栈的讲解我在题解[739. 每日温度](https://programmercarl.com/0739.每日温度.html)中已经详细讲解了。
|
||
|
||
本篇我侧重与说一说，如何处理循环数组。
|
||
|
||
相信不少同学看到这道题，就想那我直接把两个数组拼接在一起，然后使用单调栈求下一个最大值不就行了！
|
||
|
||
确实可以！
|
||
|
||
将两个nums数组拼接在一起，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集即result数组resize到原数组大小就可以了。
|
||
|
||
代码如下：
|
||
|
||
```CPP
|
||
// 版本一
|
||
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。
|
||
|
||
代码如下：
|
||
|
||
```CPP
|
||
// 版本二
|
||
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;
|
||
}
|
||
};
|
||
```
|
||
|
||
可以版本二不仅代码精简了，也比版本一少做了无用功！
|
||
|
||
最后在给出 单调栈的精简版本，即三种情况都做了合并的操作。
|
||
|
||
```CPP
|
||
// 版本二
|
||
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:
|
||
|
||
```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:
|
||
> 版本一：
|
||
|
||
```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
|
||
```
|
||
|
||
> 版本二：针对版本一的优化
|
||
|
||
```python
|
||
class Solution:
|
||
def nextGreaterElements(self, nums: List[int]) -> List[int]:
|
||
res = [-1] * len(nums)
|
||
stack = []
|
||
#第一次遍历nums
|
||
for i, num in enumerate(nums):
|
||
while stack and num > nums[stack[-1]]:
|
||
res[stack[-1]] = num
|
||
stack.pop()
|
||
stack.append(i)
|
||
#此时stack仍有剩余，有部分数‘无下一个更大元素’待修正
|
||
#第二次遍历nums
|
||
for num in nums:
|
||
#一旦stack为空，就表明所有数都有下一个更大元素，可以返回结果
|
||
if not stack:
|
||
return res
|
||
while stack and num > nums[stack[-1]]:
|
||
res[stack[-1]] = num
|
||
stack.pop()
|
||
#不要将已经有下一个更大元素的数加入栈，这样会重复赋值，只需对第一次遍历剩余的数再尝试寻找下一个更大元素即可
|
||
#最后仍有部分最大数无法有下一个更大元素，返回结果
|
||
return res
|
||
```
|
||
|
||
### Go:
|
||
|
||
```go
|
||
// 版本一
|
||
func nextGreaterElements(nums []int) []int {
|
||
// 拼接一个新的nums
|
||
numsNew := make([]int, len(nums) * 2)
|
||
copy(numsNew, nums)
|
||
copy(numsNew[len(nums):], nums)
|
||
// 用新的nums大小来初始化result
|
||
result := make([]int, len(numsNew))
|
||
for i := range result {
|
||
result[i] = -1
|
||
}
|
||
|
||
// 开始单调栈
|
||
st := []int{0}
|
||
for i := 1; i < len(numsNew); i++ {
|
||
if numsNew[i] < numsNew[st[len(st)-1]] {
|
||
st = append(st, i)
|
||
} else if numsNew[i] == numsNew[st[len(st)-1]] {
|
||
st = append(st, i)
|
||
} else {
|
||
for len(st) > 0 && numsNew[i] > numsNew[st[len(st)-1]] {
|
||
result[st[len(st)-1]] = numsNew[i]
|
||
st = st[:len(st)-1]
|
||
}
|
||
st = append(st, i)
|
||
}
|
||
}
|
||
result = result[:len(result)/2]
|
||
return result
|
||
}
|
||
```
|
||
|
||
```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:
|
||
|
||
```JS
|
||
/**
|
||
* @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：
|
||
|
||
```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:
|
||
|
||
```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()
|
||
}
|
||
}
|
||
```
|
||
|
||
> 版本二：
|
||
|
||
```rust
|
||
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
|
||
}
|
||
}
|
||
```
|
||
|
||
|