【3.6】LeetCode每日一题· 下一个更大元素 II

2021年03月06日 13时06分

标签： LeetCode 栈

## 题目描述
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

#### 示例
	输入: [1,2,1]
	输出: [2,-1,2]
	解释: 第一个 1 的下一个更大的数是 2；
	数字 2 找不到下一个更大的数； 
	第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

**注意：**输入数组的长度不会超过 10000。

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/next-greater-element-ii/ "题目链接")

## 解题思路
使用暴力解法需要首先对每一个元素进行遍历，同时在每一轮中，需要对遍历到的元素后的所有元素进行遍历，找出第一个比它大的元素。时间复杂度$$O(N^2)$$显然会超时。

考虑这样一个序列`[6, 6, 4, 3, 7]`，如果采用朴素的暴力解法，那我们在外层循环遍历到6时，需要在内层循环遍历`[6, 4, 3, 7]`四个元素；在外层循环遍历到5时，内存循环遍历`[4, 3, 7]`三个元素……

实际上，由于`[6, 6, 4, 3]`组成了一个非递增数列，因此它们之后第一个更大元素一定相同，都为`7`。换句话说，**如果某一段元素是单调递减的，那么他们的下一个最大元素相同**。朴素的暴力解法浪费了这一信息。

基于此，我们维护一个**单调栈**，栈中保存的是数组下标，并满足从栈底到栈顶有

$$nums[i] \leq nums[i+1], $$

即元素单调递减。那么当遍历到数组某一个元素`nums[i]`时，
1. 如果栈为空，则将`i`压入栈；
2. 如果栈非空，访问栈顶元素。
	* 如果栈顶元素在数组中对应的值比`nums[i]`小，则不断出栈，直到栈顶元素对应的值比`nums[i]`大为止。那么这些出栈的元素对应值的**下一个更大元素** 都为 `nums[i]`。
	* 否则说明`nums[i]`继续组成递减数列，将`i`压入栈中。
注意到题目要求实现“循环数组”。可以使用取模运算来实现。另外，可以将原数组的前`i+1`个数字拷贝到数组最后，形成一个新的数组。由于本题中最多遍历数组两遍，因此只需拷贝一次即可。

## 代码
	class Solution {
	public:
		vector<int> nextGreaterElements(vector<int>& nums) {
			const int N = nums.size();
			vector<int> res(N, -1);
			stack<int> st;
			for(int i = 0; i < 2*N-1; i++){
				if(st.empty()){
					st.push(i%N);
				}else{
					while(!st.empty() && nums[st.top()]<nums[i%N]){
						res[st.top()] = nums[i%N];
						st.pop();
					}
					st.push(i%N);
				}
			}
			return res;
		}
	};

#### 用时和内存
> 执行用时：40 ms，在所有 C\++提交中击败了81.25%的用户
> 内存消耗：22.6 MB，在所有 C\++提交中击败了68.15%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.6】LeetCode每日一题· 下一个更大元素 II

所有评论

暂无评论

新增评论