1. 代码段小站首页
  2. 算法

leetcode503-下一个更大元素II

彭晨涛 • • 算法 • 阅读 9

原题

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

示例1:

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

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

解法

思想

单调栈，维持一个递减的栈，将数组的下标入栈，遇到一个比栈顶元素对应值大的元素弹出栈顶元素，直到栈顶元素比该元素值大，压入该元素。循环搞两次。

代码

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        boolean[] mark = new boolean[nums.length];
        int[] ans = new int[nums.length];
        for(int n = 0;n<2;n++){
            for(int i = 0;i<nums.length;i++){
                while(!stack.isEmpty()&&nums[i]>nums[stack.peek()]){
                    int index = stack.pop();
                    ans[index] = nums[i];
                    mark[index] = true;
                }
                if(!mark[i])  stack.push(i);
            }
        }

        for(int i = 0;i<ans.length;i++)
            if(!mark[i]) ans[i] = -1;
        return ans;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode503-%e4%b8%8b%e4%b8%80%e4%b8%aa%e6%9b%b4%e5%a4%a7%e5%85%83%e7%b4%a0ii/

赞 (0)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年1月31日 19:08
下一篇 2020年2月1日 19:27

相关推荐

  • leetcode706-设计哈希映射

    原题 不使用任何内建的哈希表库设计一个哈希映射 具体地说，你的设计应该包含以下的功能 put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更...

    彭晨涛 彭晨涛
    算法 2019年12月18日
    0110

  • leetcode64-最小路径和

    原题 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明： 每次只能向下或者向右移动一步。 示例: 输入： [ [1,3...

    彭晨涛 彭晨涛
    算法 2020年2月24日
    050

  • leetcode914-卡牌分组

    原题 给定一副牌，每张牌上都写着一个整数。 此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组： 每组都有 X 张牌。 组内所有的牌上都写着相同的整数。...

    彭晨涛 彭晨涛
    算法 2020年3月27日
    080

  • leetcode53-最大子序和

    原题 原题 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 输入： [-2,1,-3,4,-1,2,1,-5,4],...

    彭晨涛 彭晨涛
    算法 2020年2月20日
    090

  • leetcode210-课程表II

    原题 现在你总共有 n 门课需要选，记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0...

    彭晨涛 彭晨涛
    算法 2020年5月17日
    0100
  • 剑指offer35-复杂链表的复制 算法

    剑指offer35-复杂链表的复制

    原题（来源Leetcode） 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random ...

    彭晨涛 彭晨涛
    2020年6月13日
    080

  • leetcode682-棒球比赛

    原题 你现在是棒球比赛记录员。给定一个字符串列表，每个字符串可以是以下四种类型之一：1. 整数（一轮的得分）：直接表示您在本轮中获得的积分数。2. "+"（一轮的得...

    彭晨涛 彭晨涛
    算法 2020年2月3日
    0150

  • leetcode263-丑数

    原题 编写一个程序判断给定的数是否为丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例1: 输入： 6 输出： true 解释： 6 = 2 × 3 示例2: 输入： ...

    彭晨涛 彭晨涛
    算法 2020年2月6日
    080

  • leetcode705-设计哈希集合

    原题 不使用任何内建的哈希表库设计一个哈希集合 具体地说，你的设计应该包含以下的功能 add(value)：向哈希集合中插入一个值。 contains(value) ：返回哈希集合...

    彭晨涛 彭晨涛
    算法 2019年12月18日
    090

  • leetcode695-岛屿的最大面积

    原题 给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围...

    彭晨涛 彭晨涛
    算法 2020年3月15日
    01220

发表回复

登录后才能评论