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

相关推荐

  • leetcode365-水壶问题

    原题 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？ 如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升...

    彭晨涛 彭晨涛
    算法 2020年3月21日
    0180

  • leetcode385-迷你语法分析器

    原题 给定一个用字符串表示的整数的嵌套列表，实现一个解析它的语法分析器。 列表中的每个元素只可能是整数或整数嵌套列表 提示： 你可以假定这些字符串都是格式良好的： 字符串非空 字符...

    彭晨涛 彭晨涛
    算法 2020年1月28日
    02150

  • leetcode78-子集

    原题 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明： 解集不能包含重复的子集。 示例: 输入: nums = [1,2,3] 输出: [ [3...

    彭晨涛 彭晨涛
    算法 2020年5月24日
    0300

  • leetcode76-最小覆盖子串

    原题 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。 示例: 输入: S = "ADOBECODEBANC", T = "ABC" 输...

    彭晨涛 彭晨涛
    算法 2020年5月23日
    0140

  • leetcode820-单词的压缩编码

    原题 给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。 例如，如果这个列表是 ["time", "me", "bell"]，我们就可以将其表示为 S ...

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

  • leetcode771-宝石与石头

    原题 给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。 J 中的字母不重复，J ...

    彭晨涛 彭晨涛
    算法 2019年12月26日
    0200

  • leetcode341-扁平化嵌套列表迭代器

    原题 给定一个嵌套的整型列表。设计一个迭代器，使其能够遍历这个整型列表中的所有整数。 列表中的项或者为一个整数，或者是另一个列表。 示例1： 输入: [[1,1],2,[1,1]]...

    彭晨涛 彭晨涛
    算法 2020年1月27日
    050

  • 程序员面试金典17.01-不用加号的加法

    原题（来源Leetcode） 设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。 示例: 输入: a = 1, b = 1 输出: 2 提示： a, b 均可能是负数或...

    彭晨涛 彭晨涛
    算法 2020年6月9日
    0560

  • leetcode153-寻找旋转排序数组中的最小值

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，...

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

  • leetcode105-从前序与中序遍历序列构造二叉树

    原题 根据一棵树的前序遍历与中序遍历构造二叉树。 注意:你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inord...

    彭晨涛 彭晨涛
    算法 2020年1月13日
    090

发表回复

登录后才能评论