每日一练:LeeCode-503. 下一个更大元素 II (中)【单调栈】

发布时间:2024年01月02日

本文是力扣LeeCode-503. 下一个更大元素 II 学习与理解过程,本文仅做学习之用,对本题感兴趣的小伙伴可以出门左拐LeeCode。

给定一个循环数组 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]

在这里插入图片描述
单调栈法:单调栈法是我们刷算法必备的黄金公式
对单调栈的理解我参考 负雪明烛博主的讲解
在实现上,我们可以使用**「单调栈」**来实现,单调栈是说 栈里面的元素从栈底到栈顶单调递增或者单调递减的(类似于汉诺塔)。本题应该用个「单调递减栈」来实现。
建立「单调递减栈」,并对原数组遍历一次:
如果栈为空,则把当前元素放入栈内;
如果栈不为空,则需要判断当前元素和栈顶元素的大小:
如果当前元素比栈顶元素大:说明当前元素是前面一些元素的「下一个更大元素」,则逐个弹出栈顶元素,直到当前元素比栈顶元素小为止。
如果当前元素比栈顶元素小:说明当前元素的「下一个更大元素」与栈顶元素相同,则把当前元素入栈。

模版:以 下一个更大元素 I 为例

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = nums2.length - 1; i >= 0; --i) {
            int num = nums2[i];
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }
            map.put(num, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++i) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }
}

思路

考虑到本题的实际情况,需要回过头来遍历数组,这里牵扯到 循环数组 的概念。
循环数组数组的最后一个元素下一个元素是数组的第一个元素,形状类似于「环」。我们只需要使用 取模运算 % 可以把下标i映射到数组 nums长度的 0?N内。

未通过版本

参照下一个更大元素 I 的解决方法并结合循环数据,我的代码如下:

    public int[] nextGreaterElements(int[] nums) {
        int[] result = new int[nums.length];
        Map<Integer,Integer> map = nextGreaterElementsHelper(nums);
        for(int i=0;i<nums.length;i++){
            result[i] = map.get(nums[i]);
        }
        return result;
    }

    private Map<Integer,Integer> nextGreaterElementsHelper(int[] nums){
        int len = nums.length;
        Map<Integer,Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for(int j=2*len-1;j>=0;j--){	//逻辑环,取模运算
            while(!stack.isEmpty()&&stack.peek()<=nums[j%len]){
                stack.pop();
            }
            map.put(nums[j%len],stack.isEmpty()?-1:stack.peek());
            stack.push(nums[j%len]);
        }
        return map;
    }

提交报错

在这里插入图片描述
从1开始就出问题了,debug了半天,没看出问题。有大佬帮我看出问题吗?

代码实现

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

大家有更好的方法,请不吝赐教。

文章来源:https://blog.csdn.net/kdzandlbj/article/details/135331082
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。