各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 31 天。今天力扣上的每日一题是「503. 下一个更大元素 II」。

解题思路

今天题目的两个重点：

  • 如何求下一个更大的元素
    - 如何实现循环数组

1. 如何求下一个更大的元素

本题如果暴力求解，对于每个元素都向后去寻找比它更大的元素，那么时间复杂度 $O(N^2)$ 会超时。必须想办法优化。

我们注意到，暴力解法中，如果数组的前半部分是单调不增的，那么会有很大的计算资源的浪费。比如说 [6,5,4,3,8]，对于前面的 [6,5,4,3] 等数字都需要向后遍历，当寻找到元素 8 时才找到了比自己大的元素；而如果已知元素 6 向后找到元素 8 才找到了比自己的大的数字，那么对于元素 [5,4,3] 来说，它们都比元素 6 更小，所以比它们更大的元素一定是元素 8，不需要单独遍历对 [5,4,3] 向后遍历一次！

根据上面的分析可知，可以遍历一次数组，如果元素是单调递减的（则他们的「下一个更大元素」相同），我们就把这些元素保存，直到找到一个较大的元素；把该较大元素逐一跟保存了的元素比较，如果该元素更大，那么它就是前面元素的「下一个更大元素」。

在实现上，我们可以使用「单调栈」来实现，单调栈是说栈里面的元素从栈底到栈顶是单调递增或者单调递减的（类似于汉诺塔）。

本题应该用个「单调递减栈」来实现。

建立「单调递减栈」，并对原数组遍历一次：

  • 如果栈为空，则把当前元素放入栈内；
  • 如果栈不为空，则需要判断当前元素和栈顶元素的大小：
    • 如果当前元素比栈顶元素大：说明当前元素是前面一些元素的「下一个更大元素」，则逐个弹出栈顶元素，直到当前元素比栈顶元素小为止。
    • 如果当前元素比栈顶元素小：说明当前元素的「下一个更大元素」与栈顶元素相同，则把当前元素入栈。

可以用下面的动图来帮助理解：

2. 如何实现循环数组

题目说给出的数组是循环数组，何为循环数组？就是说数组的最后一个元素下一个元素是数组的第一个元素，形状类似于「环」。

一种实现方式是，把数组复制一份到数组末尾，这样虽然不是严格的循环数组，但是对于本题已经足够了，因为本题对数组最多遍历两次。
另一个常见的实现方式是，使用取模运算 % 可以把下标 i 映射到数组 nums 长度的 0 ~ N 内。

代码

栈里面需要保存元素在数组中的下标，而不是具体的数字。因为需要根据下标修改结果数组 res。

  1. class Solution(object):
  2.     def nextGreaterElements(self, nums):
  3.         """
  4.         :type nums: List[int]
  5.         :rtype: List[int]
  6.         """
  7.         N = len(nums)
  8.         res = [-1] * N
  9.         stack = []
  10.         for i in range(N * 2):
  11.             while stack and nums[stack[-1]] < nums[i % N]:
  12.                 res[stack.pop()] = nums[i % N]
  13.             stack.append(i % N)
  14.         return res
  • 时间复杂度：$O(N)$，遍历了两次数组；
  • 空间复杂度：$O(N)$，使用了额外空间「单调栈」，最坏情况下，栈内会保存数组的所有元素。

刷题心得

单调栈是神器之一，虽然考察的不多，但是需要学会。

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！