太原网络推广网站,自己怎么开发社交app软件,最近的电脑培训学校,宁波南部商务区网站建设文章目录 Tag题目来源题目解读解题思路方法一#xff1a;单调栈循环数组 写在最后 Tag
【单调栈循环数组】【数组】 题目来源
503. 下一个更大元素 II 题目解读
在循环数组中找下一个更大的元素。循环数组指的是#xff0c;数组的最后一个元素的下一个元素是数组首元素。 … 文章目录 Tag题目来源题目解读解题思路方法一单调栈循环数组 写在最后 Tag
【单调栈循环数组】【数组】 题目来源
503. 下一个更大元素 II 题目解读
在循环数组中找下一个更大的元素。循环数组指的是数组的最后一个元素的下一个元素是数组首元素。 解题思路
本题的数据规模为 1 0 4 10^4 104暴力枚举的时间复杂度为 1 0 8 10^8 108应该还是可以通过的这里就不对暴力枚举的方法进行介绍了读者可自行解决练练基本功对于基本的暴力枚举代码力求书写完毕即能通过。
接下来重点介绍【单调栈哈希表】的解法也是本题最优的一个解法。
方法一单调栈循环数组
单调栈
单调栈中保存的是下标从栈底到栈顶的下标在数组 nums 中对应的值是单调不升的。
每次我们移动到数组中的一个新的位置 i我们就将当前单调栈中所有对应值小于 nums[i] 的下标弹出单调栈这些值的下一个更大元素即为 nums[i]证明很简单如果有更靠前的更大元素那么这些位置将被提前弹出栈。随后我们将位置 i 入栈。
循环数组
因为是要在循环数组中找下一个更大的元素因此需要数组 nums 的前 n-1 元素拼接在原数组序列的后面这一点我们可以使用下标取模来实现。第 i 个数用 nums[i % n] 表示。
实现代码
class Solution {
public:vectorint nextGreaterElements(vectorint nums) {int n nums.size();vectorint ans(n, -1);stackint stk; // 栈存储的是下标for(int i 0; i 2*n - 1; i){while(!stk.empty() nums[stk.top()] nums[i % n]){ans[stk.top()] nums[i % n];stk.pop();}stk.push(i % n);}return ans;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) n n n 是数组 nums 的长度。每个元素值最多被遍历两次每个元素值入栈、出栈次数最多一共 4 次。
空间复杂度 O ( n ) O(n) O(n)。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
