题目描述
输入:循环数组
输出:从左往右遍历第一个比数组中对应位置元素大的数值
样例
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2;
数字 2 找不到下一个更大的数;
第二个 1 的下一个最大的数需要循环搜索,结果也是 2。
算法1
(单调栈) $O(n)$
此题为单调栈类题目,其思路跟双指针类似,首先先思考暴力解法,然后再在暴力解法的基础上进行优化。
首先先不考虑循环数组,在简单的数组中,暴力解法的做法为两重循环$O(n^2)$。首先第一重循环遍历数组每个元素本身$i$,第二重循环再从$i+1$的位置往右遍历直到遍历到一个比该元素更大的数。然后我们可以观察到,假如数组中存在$j,k (j < k)$,而且$nums[j]>=nums[k]$,则无论如何都不会遍历到k而会在i到j中找到更大的数;假如在此区间内无法找到,也不会取$nums[k]$,因为此时$nums[i]>nums[j]>=nums[k]$。这就是单调栈单调的来源。
然后通过观察数组的遍历特点可以发现,当$i$的位置越靠近数组的末端,则越难找到比它大的数(因为右侧数的数量在减少)。当$i$就是最右端的数时,不能找到比他更大的数。因此,我们需要从右往左进行遍历;同时,由于我们储存数的顺序(即真正的遍历顺序)总是在题目要求的遍历的顺序的相反方向(即从右往左遍历时,先遍历到$k$再遍历到$j$,而在遍历到$k$时储存的数会在遍历$j$时释放),因此需要使用先进后出的栈结构来对相应的数进行储存,这样我们最先储存的数会在最后才被拿来与$i$做比较。
在回到题目本身,这个题目还加上了循环数组的限制,因此我们需要可以使用一个trick,即在原数组右侧再复制一份相同的数组再进行反向遍历,并在右半的$n$个数中不进行结果输出。这是因为假设数组中存在$l,m,n(l < m < n)$且$nums[m]>nums[n]>nums[l]$,而假设$n$右侧没有比它更大的数,则必定会通过循环找到满足条件的$m$,就等价于访问了右侧复制的一份数组中的元素。而$l$由于已经在$m$前访问过并不满足条件,就算再在数组后面复制一次也是没有用的;而就算$m$右侧还有比$m$更大的数,但因为我们只需要找第一个更大的数,因此也不需要访问。因此,只需要在右侧再复制一份数组,使得在从右往左遍历,遍历到左半时已经有完整遍历了右半数组所有元素的单调栈即可。
C++ 代码
stack<int> st;
vector<int> ans(nums.size());
nums.insert(nums.end(),nums.begin(),nums.end());
for(int i=nums.size()-1;i>=0;i--)
{
while(!st.empty() && st.top()<=nums[i])//注意是小于等于而不是小于,不然会WA
{
st.pop();
}
if(i<nums.size()>>1)
{
if(st.empty())
ans[i]=-1;
else
ans[i]=st.top();
}
st.push(nums[i]);
}
return ans;