LeetCode 503：下一个更大元素Ⅱ（取模实现循环数组+单调栈）

题目

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

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

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

示例 2:
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

提示:
1 <= nums.length <= 104
-109 <= nums[i] <= 109

思路

这种找左/右下一个更大/更小的元素的，应该想到单调栈。因为譬如，4 3 2 8这个数组，我们发现4 3 2因为具有单调递减的性质，所以它们的下一个更大的元素是一样的，都是8。所以本题我们应该维护一个单调递减栈。每次元素出栈时便一定是被它的下个更大元素给踢出栈了，也就是说，出栈也就意味着找到自己的下个更大元素。
但是仅仅是维护一个单调递减栈是无法找出所有元素的下个更大的数的。譬如4 3 2 8 1。最后的1只会入栈，也就找不到自己的下个更大元素。
为此我们应该循环遍历数组，或者说实现循环数组。**实现循环数组一般要么是复制n份数组拼接到原数组后，或者将数组扩大n倍后取模使得下标依旧映射在原数组下标内。**这个n要看具体题目而定，譬如本题，最多只会遍历两遍数组就能将所有数的下个更大元素找到。

java代码

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        LinkedList<Integer> stack = new LinkedList<>();
        int len = nums.length;
        int[] result = new int[len];
        for(int i=0;i<len;i++) result[i]=-1;
        for(int i=0;i<2*len-1;i++){
            while(!stack.isEmpty()&&nums[i%len]>nums[stack.peek()]){
                result[stack.peek()]=nums[i%len];
                stack.pop();
            }
            stack.push(i%len);
        }
        return result;
        
    }
}

效率

5ms，击败93.63%使用 Java 的用户。不用再优化了。