【LeetCode】下一个更大元素 II Java 题解

关注

发布于: 2021 年 03 月 06 日

题目

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

代码

public class DayCode {    public static void main(String[] args) {        int[] nums = new int[]{1, 2, 1};        int[] ans = new DayCode().nextGreaterElements(nums);        System.out.println("ans is " + Arrays.toString(ans));    }
    /**     * 链接：https://leetcode-cn.com/problems/next-greater-element-ii     * 时间复杂度O(n * n)     * 空间复杂度O(n)     * @param nums     * @return     */    public int[] nextGreaterElements(int[] nums) {        int n = nums.length;        int[] ans = new int[n];
        int[] tempNums = new int[2 * n];        for (int i = 0; i < n; i++) {            tempNums[i] = nums[i];            tempNums[n + i] = nums[i];        }
        Map<Integer, Integer> map = new HashMap<>(n);        for (int i = 0; i < n; i++) {            for (int j = i + 1; j < 2 * n && j < n + i; j++) {                if (tempNums[j] > tempNums[i]) {                    map.put(i, tempNums[j]);                    break;                }            }        }
        for (int i = 0; i < n; i++) {            ans[i] = map.getOrDefault(i, -1);        }        return ans;    }}

复制代码

单调栈优化

public class DayCode {    public static void main(String[] args) {        int[] nums = new int[]{1, 2, 1};        int[] ans = new DayCode().nextGreaterElements(nums);        System.out.println("ans is " + Arrays.toString(ans));    }
    /**     * 链接：https://leetcode-cn.com/problems/next-greater-element-ii          * 时间复杂度O(n)     * 空间复杂度O(n)     * @param nums     * @return     */    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;    }}

复制代码

总结

今天的题目看着简单，我首先用暴力方法提交了一次，提交不通过，优化之后才明白题目的含义。暴力方法虽然时间复杂度不优，但是帮助我们理解题意还是很有帮助！
优化后的方法使用的单调栈，降低了算法时间复杂度。
坚持每日一题，加油！

发布于: 2021 年 03 月 06 日阅读数: 16

原文链接:【http://xie.infoq.cn/article/a31f992d846e9366d8ad70a8b】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】下一个更大元素 II Java 题解

题目

代码

总结

HQ数字卡

评论