【LeetCode】下一个更大元素单调栈 Java 题解

作者：Albert

2022-10-22
北京
本文字数：951 字
阅读完需：约 3 分钟

题目描述

给定一个循环数组 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]链接:  https://leetcode.cn/problems/next-greater-element-ii/description/

复制代码

思路分析

今天的算法题目是数组类型的题目。首先分析题目，题目给出的是循环数组，我们需要查找下一个比他大的元素。注意，这里的下一个是指这个数字之后的第一个比它更大的数。对于循环数组，我们一般的处理思路是数组直接拷贝一下，构造成长度是 2 倍的数组。然后依次遍历的每一个元素去寻找，这种做法的思路比较简单，但是有的测试用例不能通过。
那还有什么方法呢？单调栈的方法也比较常用。什么是单调栈？顾名思义，单调栈即满足单调性的栈结构。对于这个题目，我们维护一个单调递增的栈，我们在栈中存储的元素是 nums 的下标。在实际操作中，我们首先定义一个长度为 n 的 ans,由于找不到的下一个更大的元素时候，答案是-1。我们先将 ans 数组赋值为-1。然后依次处理每一个元素，与栈顶元素比较大小，当前元素的值比栈顶元素大的时候，则栈顶元素出栈，栈顶元素找到了大于他的下一个元素。
具体实现代码如下，供参考。

通过代码

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