题目描述

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

示例 1:

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/next-greater-element-ii

算法思路

概述

做一道算法题，具体从两方面出发，一是题目性质，二是数据范围。从题目性质中我们往往可以找出该题应该用什么算法思路，而数据范围则决定我们应该用什么数据结构来优化我们的算法，本题是一个经典的单调栈题目，但为什么使用单调栈，如何分析出来使用单调栈，待我下面一一说明。

题目分析

首先根据题目性质，我们得知题目给我们的是一个循环数组，也就是首尾相连。我们先不考虑首尾相连，单单从"输出每个元素的下一个更大元素"这一主要问题入手，也就是说我们现在把问题简化成："给你一个数组，让你求出每一个元素右边离他最近的比它大的元素，如果不存在就是-1"。

这其实就是一个单调栈裸题，单调栈的模型就是用来解决"找到某个元素左边/右边比它大的最近的一个数"这一类问题，下面我将讲解一下单调栈模型，如果了解过单调栈模型的同学可以跳过。

单调栈模型

正常来说，我们对于每个元素求其最近比它大的元素，都是通过双重for循环，第一重枚举元素，第二重循环从当前这个元素出发，往左(或右)扫描数组，若出现比其大的就记录下来。

这种做法当然可行，只不过它的时间复杂度是O(n^2)的，为了优化效率，就可以使用单调栈，它是 解决"找到某个元素左边/右边比它大的最近的一个数"的经典数据结构。可以将时间复杂度优化到O(n)。

为了讲解简单，我们按照题意找的是右边比当前元素大的最近一个数，理解后可以很容易写出距离左边最近的代码。

单调栈思想

单调栈的思想是，从右往左遍历，每次遍历的时候维护一个栈，如果当前元素大于等于栈顶，那么将栈顶弹出（这是一个循环的过程，每次弹出后都需要再判断一下是否大于栈顶元素），直到栈为空或者栈顶元素大于当前元素。如果此时栈不为空，那么栈顶元素就是当前元素右边比它大的最近的一个数。然后将当前元素存到栈中。

怎么样，如果你是第一次接触单调栈模型，那么你一定会感到十分迷惑，不急，下面来证明一下这个单调栈模型是正确的。

单调栈证明

我们从右往左维护一个栈，这个栈其实是单调递减的。如何证明呢，我们只需要将目光聚集在栈的插入和弹出操作就能发现：弹出操作在元素入栈前，元素会将栈中比它大的元素都弹出，然后再插入到栈顶。那么有的小伙伴就要问了，如果插入的时候栈不为空，如何保证此时栈是单调递减的呢？其实我们只需要看第一步，也就是最开始的时候栈是空的，我们会直接将最末尾的元素放到栈中，后续就一直维护这个栈，是可以保证整个栈的单调性的。

复杂度分析

可以发现，我们对于每个元素只会入栈一次，出栈一次。

再来理解一个点，我们是从右往左插入元素的，因此在栈中，数组靠右的元素在栈底，靠左的元素在栈顶，也就是说右边越靠近当前元素的位置就是栈顶。所以说，我们当前元素会将所有比他小的元素弹出，此时如果栈不为空，那么栈顶元素就是它右边比他大的最近的一个。

继续题目分析

理解了单调栈模型后，我们再来看一下这道题目，它给的是一个循环数组，那么很多时候处理循环数组最有效的方式就是"破环成链"，直接将其展开——把数组复制一遍拼接到当前数组的尾部。然后我们同样的按照单调栈的作法，就可以找到右边比他大的最近的一个数了。

暴力做可以不可以，当然可以，可以双重for循环来解决，但是不要忘了看一下数据范围：注意: 输入数组的长度不会超过 10000。. 一般来说数据范围在10000的就只能用O(n), O(n ^ 2)的复杂度会超时。所以这题的正解就是单调栈。

AC代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */

// 封装获取栈顶元素的函数
Array.prototype.top = function() {
    return this[this.length - 1];
}

var nextGreaterElements = function(nums) {
    nums = [...nums, ...nums]; // 破环成链
    const n = nums.length;
    const stk = [], ans = [];
    for(let i = n - 1; ~i; -- i) {
        while(stk.length && nums[stk.top()] <= nums[i]) stk.pop(); // 如果当前元素大于等于栈顶元素，栈顶出栈
        if(i < n / 2) {
        	// 记录答案
            if(stk.length) ans[i] = nums[stk.top()]; 
            else ans[i] = -1;
        }
        stk.push(i);
    }
    return ans;
};

总结

单调栈刚开始接触不好理解，特别是对没有算法基础的同学。可以先收藏然后慢慢看，当做开阔眼界，没必要给自己太大的压力来学习。学习知识嘛，我向来都比较享受，有一种探知的乐趣，就感觉很好玩。如果有同学对算法和前端感兴趣的，可以联系我，我们一起讨论，一起玩。