Q503 Next Greater Element II

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number.

Example 1:
Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number; 
The second 1's next greater number needs to search circularly, which is also 2.

Note: The length of given array won't exceed 10000.

解题思路:

题意为:给一个循环列表(最后一个元素与第一个元素相同),求出列表中每个元素的下一个较大的元素是什么(最大值没有下一个较大的元素,对应位置为-1)。

以 nums = [100,9,1,11,1,120,111,123,1,-1,-100,103,98,100] 为例,我们可以观察到几个性质:

  • 在最大值(123)左侧,如果前面的数比后面的数小,则把后面的数当做较大值(如 9 < 11);
  • 在最大值(123)右侧,如果一直到列表结束都找不到较大的数(如103),则需要重新再遍历一次列表,找到下一个较大的数(120)。
  1. 思路一:
  • 设置两个指针 i 和 j,i 始终指向当前元素。然后,将 nums 扩宽 2 倍,j 每次指向下一个较大的元素。当 i 的指针达到原 nums 的长度,则退出循环。注意,当 i 指向 103,j 向后找到 120,然后,j 还要回退到 i 的下一个位置,不然,98就找不到下一个较大的数 100。这种情况下,最坏时间复杂度为 O(n^2),Python3 版本会超时(C++ 和 Java不会)。
  1. 思路二:
  • 使用一个栈,遍历列表,栈中存放还未确定下一个较大元素的下标,如果遇到一个较大的数,则进入一个新的循环,把未确定的元素出栈,直到栈中留下的元素比当前的元素大。(比如,[100,9,1] 都先放入栈中,因为它们都还未找到较大的元素,下一次,遇到 11,则 1 比 11 小,1 出栈;此时继续循环判断栈中的 9, 9 也比 11 小,9 出栈;100 比 11 大,则栈中元素不能在确定下一个较大的元素了,则 11 入栈,继续遍历列表)。
  • 当一次遍历结束后,只有 [123,103,100] 还在栈中。这时,只需要重新再次遍历一遍列表,100 比 120 小,出栈;103 比 120 小,出栈;直到再次遇到最大数123,则循环结束。
  • 因为不涉及指针回退,则时间复杂度 O(n),但空间复杂度 O(n)
Python 实现:
class Solution:
    # 超时版本:最坏时间复杂度为 O(n^2)
    def nextGreaterElements(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        lens = len(nums)
        if lens == 0:
            return []
        maxnum = max(nums)  # nums 中的最大值
        nums = nums + nums  # 将 nums 扩展成 2 倍长
        ret = []  # 返回值
        i = j = 0 # i 指向当前数,j 指向下一个较大数
        while i < lens:
            if nums[i] == maxnum: # 最大值位置直接为 -1
                ret.append(-1)
                i += 1; j += 1
            elif nums[i] < nums[j]:
                ret.append(nums[j])
                i += 1; j = i + 1  # j 指针回退
            else:
                j += 1
        return ret

    # AC版本:最坏时间复杂度为 O(n),但空间复杂度也为 O(n)
    def nextGreaterElements2(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        lens = len(nums)
        if lens == 0:
            return []
        maxnum = max(nums)  # nums 中的最大值
        ret = [-1] * lens   # 返回值
        stack = []  # 存储还未确定的下一个较大数的元素
        for i in range(lens):
            while stack and nums[stack[-1]] < nums[i]:
                ret[stack.pop()] = nums[i]
            stack.append(i)
        # print(stack)

        for i in range(lens):
            while stack and nums[stack[-1]] < nums[i]:
                ret[stack.pop()] = nums[i]
            if maxnum == nums[i]:
                break
        return ret

a = [3,1,4,2,5,3]
a = [3,5,4,2,5,1,3]
a = [3,1,5,4,6,5,2,6,5,4,3]
a = [6,5,3,1,4,5,6,7,6,5,4,3,2,6]
a = [100,9,1,11,1,120,111,123,1,-1,-100,103,98,100]
print(Solution().nextGreaterElements2(a)) 
# [120, 11, 11, 120, 120, 123, 123, -1, 103, 103, 103, 120, 100, 120]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[剑指offer] 栈的压入、弹出序列 [剑指offer] 栈的压入、弹出序列

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序...

1212
来自专栏java学习

请问你知道什么是栈吗?

1.1栈的概念及记本操作 栈(stack)又称堆栈,是限制在表的一端进行插入和删除的线性表。其限制是仅允许在表的一端进行插入和删除操作,不允许在其他任何位置进行...

3208
来自专栏java学习

重要通知!小编出新的Java练习题咯!!

正确答案 3月5号公布 一、选择题和问答题 1、在一个java原文件中,import, class, package语句的顺序是( )。 A. import ...

4665
来自专栏智能算法

程序员必须了解的数据结构:Array、HashMap 与 List

当开发程序时,我们(通常)需要在内存中存储数据。根据操作数据方式的不同,可能会选择不同的数据结构。有很多常用的数据结构,如:Array、Map、Set、List...

1380
来自专栏python全栈布道师

2017年8月28日技术日记

4276
来自专栏个人随笔

Java 关于集合框架那点事儿

 1.引入集合框架   采用数组存在的一些缺陷:    1.数组长度固定不变,不能很好地适应元素数量动态变化的情况。    2.可通过数组名.length获取数...

29610
来自专栏androidBlog

笔试题—字符串常见的算法题集锦

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

1621
来自专栏老马说编程

(54) 剖析Collections - 设计模式 / 计算机程序的思维逻辑

上节我们提到,类Collections中大概有两类功能,第一类是对容器接口对象进行操作,第二类是返回一个容器接口对象,上节我们介绍了第一类,本节我们介绍第二类。...

2549
来自专栏赵俊的Java专栏

快乐数

2583
来自专栏Golang语言社区

【Go 语言社区】POJ 1047 Round and Round We Go 循环数新解

题目描述: 给定一字符串表示的高精度数,判断它是否是可循环的。如果假设字符串num的长为n,则将num从1开始乘到n,如果每次得到的结果包含的字符元素都和a是相...

35811

扫码关注云+社区

领取腾讯云代金券