本次刷题日记的第 100 篇，力扣题为：503. 下一个更大元素 II
一、题目描述：
继续来二刷下一个更大元素，本次是分享 503. 下一个更大元素 II
二、这道题考察了什么思想？你的思路是什么？
题目的要求和上次差不多，都是让我们找到数组中每一个元素的下一个更大的元素，但是本次题目中没有两个数组了，而是只有一个 nums 数组，但是这个数组是需要当做循环数组来进行处理
- 题目要求咱们按照顺序遍历 nums 数组，且找到每一个元素对于循环数组中的下一个更大的元素，如果有，则记录实际数据，如果没有，则记录 -1，最终返回结果数组
分析
本题看上去感觉比上一次的题目要简单，毕竟没有那么条件变量，只需要关注循环数组，和如何找到下一个更大的元素就可以了
对于寻找下一个更大的元素，实际上上一篇刷题文章中，我们已经分享过思路，其实本次的寻找思路和上次是一样的，只不过咱们入栈的数据稍微有点变动，本次入栈的数据是元素在 nums 中的索引，思路如下：
- 遍历数组 nums，如果栈为空，则将元素的索引入栈
- 如果栈不为空，则判断当前的数据是否大于栈顶索引对应的值，如果是大于，则将当前栈顶索引对应的结果，赋值为 当前遍历到的值，此时说明，当前栈顶索引对应的值的下一个更大值就是当前比那里到的值
- 当然，如果判断当前的数据不大于栈顶索引对应的值，则将当前的值对应的索引加入到栈顶即可
- 直到将数组遍历完毕，即可得到结果
那么上述思路仅仅是单调栈的思路，可是对于循环数组，咱们需要如何处理呢？
其实循环数组，实际上就是将数组的前 n-1 个元素，追加到 nums 后面即可，这样就可以模拟循环数组了，当然，我们也没有必要直接把循环数组拉直，咱们只是遍历 n+n-1 个元素，但是对于数据在 nums 中的索引，我们可以通过取模来得到，例如 i%n
那么结合上面的说到的单调栈 + 循环数组的方式来处理题目，我们推演一下题目给出的示例：
nums = [1,2,1]
模拟的时候，便于咱们查看，我们可以看到我们是在遍历这样的数组
| 索引 | 0 | 1 | 2 | 0 | 1 |
| 原数组 | 1 | 2 | 1 | 1 | 2 |
根据上图的推演，咱们通过示例的入栈，出栈，模拟了咱们单调栈和循环数组的整个流程，此处的可以看到索引是，0,1,2,0,1
相信对于上述的单调栈和循环数组的处理方式有了一定的熟悉吧， xdm 剩下的就是来手撸代码了
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码
- 编码的时候注意咱们的循环数组，我们的做法并没有去拉直循环数组，而是通过取模的方式来达到咱们的目的
编码如下：
func nextGreaterElements(nums []int) []int { res := make([]int, len(nums)) for i,_ := range res { res[i] = -1 } stack := []int{} length := len(nums) // 模拟循环数组 for i:=0; i<2*length-1; i++ { // 判断当前的值，大于栈顶的值，则出栈，且记录结果 // 出栈，说明，当前栈顶对应的元素的下一个更大值就是 nums[i%length] for len(stack) > 0 && nums[i%length] > nums[stack[len(stack)-1]] { res[stack[len(stack) -1]] = nums[i%length] stack = stack[:len(stack)-1] } // 数据的索引 入栈 stack = append(stack, i%length) } return res }
四、总结：
本题咱们的处理方式是使用了单调栈的方式来进行处理，时间复杂度是 O(n) ，n 即是题目给出 nums 的长度
空间复杂度是 O(n) ，n 即为咱们引入的栈空间，在极端情况下，栈占用的空间消耗是 2n-1，即所有的数据全都入栈
原题地址：503. 下一个更大元素 II
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
