外包网站制作多少钱,网站的权重,深圳关键词优化平台,wordpress more标签 无效文章目录 思路写法1完整版环形数组处理#xff1a;i取模#xff0c;遍历两遍写法2完整版#xff08;环形数组推荐写法#xff09;debug测试#xff1a;逻辑运算符短路特性result数组在栈口取元素#xff0c;是否会覆盖原有数值#xff1f; 给定一个循环数组 nums #… 文章目录 思路写法1完整版环形数组处理i取模遍历两遍写法2完整版环形数组推荐写法debug测试逻辑运算符短路特性result数组在栈口取元素是否会覆盖原有数值 给定一个循环数组 nums nums[nums.length - 1] 的下一个元素是 nums[0] 返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序这个数字之后的第一个比它更大的数这意味着你应该循环地搜索它的下一个更大的数。如果不存在则输出 -1 。
示例 1:
输入: nums [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2
数字 2 找不到下一个更大的数
第二个 1 的下一个最大的数需要循环搜索结果也是 2。示例 2:
输入: nums [1,2,3,4,3]
输出: [2,3,4,-1,4]提示:
1 nums.length 10^4-10^9 nums[i] 10^9
思路
本题属于循环数组问题循环数组的处理我们可以将两个nums数组拼接在一起使用单调栈计算出每一个元素的下一个最大值最后再把结果集即result数组resize到原数组大小即可。
但这种写法修改了nums数组而且最后还要把result数组resize回去。resize倒是不费时间是O(1)的操作但扩充nums数组相当于**多了一个O(n)**的操作。时间复杂度和空间复杂度都多了O(n)。
写法1完整版
// 版本一
class Solution {
public:vectorint nextGreaterElements(vectorint nums) {// 拼接一个新的numsvectorint nums1(nums.begin(), nums.end());nums.insert(nums.end(), nums1.begin(), nums1.end());// 用新的nums大小来初始化resultvectorint result(nums.size(), -1);if (nums.size() 0) return result;// 开始单调栈stackint st;st.push(0);for (int i 1; i nums.size(); i) { if (nums[i] nums[st.top()]) st.push(i); else if (nums[i] nums[st.top()]) st.push(i);else { while (!st.empty() nums[i] nums[st.top()]) {result[st.top()] nums[i];st.pop();}st.push(i);}}// 最后再把结果集即result数组resize到原数组大小result.resize(nums.size() / 2);return result;}
};环形数组处理i取模遍历两遍
对于这种循环数组 nums[nums.length - 1] 的下一个元素是 nums[0] 需要遍历两遍可以通过给i取模来解决
我们首先扩充for循环遍历范围令for遍历范围为[0,nums.size()*2-1]这样就遍历了2n个位置遍历长度为2n然后nums[i]改为nums[i%nums.size()]。
由于取模运算的特性 i初始值0i%nums.size()这个式子就是0--nums.size()-1循环取值。
当i初始值0时i%a的范围就是[0,a-1]
因为 “求模” 运算的定义是 “求余数”。例如当 7 除以 3结果是 2 余 1所以 7%3 的结果是 1。余数总是会小于除数的所以 i%a 的结果将始终在 0 到 a-1 的范围内。
当 i 小于 a 时i%a 的结果就是 i 自己当 i 等于 a 时i%a 的结果就是 0当 i 大于 a 时i%a 的结果就是 i-a 的值直到这个值小于 a 为止。
遍历两遍的逻辑
st.push(0);
for(int i1;inums.size()*2;i){if(nums[i%nums.size()]nums[st.top()]){st.push(i%nums.size());}else{while(nums[i%nums.size()]nums[st.top()]!st.empty()){result[st.top()]nums[i%nums.size()];st.pop();}st.push(nums[i%nums.size()]);}
}写法2完整版环形数组推荐写法
重点在只用O(n)的时间复杂度和空间复杂度完成遍历两遍数组
class Solution {
public:vectorint nextGreaterElements(vectorint nums) {stackintst;vectorintresult(nums.size(),-1);st.push(0);for(int i1;inums.size()*2;i){if(nums[i%nums.size()]nums[st.top()]){st.push(i%nums.size());}else{while(!st.empty()nums[i%nums.size()]nums[st.top()]){result[st.top()]nums[i%nums.size()];st.pop();}st.push(i%nums.size());}}return result;}
};debug测试
Line 171: Char 16: runtime error: reference binding to misaligned address 0xbebebebebebec0ba for type ‘int’, which requires 4 byte alignment (stl_deque.h) 0xbebebebebebec0ba: note: pointer points here 错误信息的意思是运行时发生了一种未定义行为Undefined Behavior。具体来说它在尝试对一个非对齐的地址即不是4字节对齐的地址进行整数的引用绑定而这个操作是未定义的。该错误通常发生在空指针解引用数组越界等情况。
这个错误出现在while循环这一句
while(nums[i%nums.size()]nums[st.top()]!st.empty())while 循环如果这么写那么在检查栈是否为空之前就已经尝试从栈顶取值这是有问题的。当栈为空时这将会导致未定义行为。
逻辑运算符短路特性
在C中逻辑AND操作符()和逻辑OR操作符(||)都具有短路特性。
对于逻辑AND操作符如果左边的操作数为假那么不论右边的操作数是什么整个表达式的结果都是假因此不需要再计算右边的操作数。对于逻辑OR操作符如果左边的操作数为真那么不论右边的操作数是什么整个表达式的结果都是真因此不需要再计算右边的操作数。
因此写单调栈的while循环while条件里面包括了非空检查的时候检查栈是否为空的语句必须放在前面确定非空之后再尝试从栈顶取值如果栈已经为空那么!st.empty()的结果为假右边的nums[i%nums.size()] nums[st.top()]就不会被执行从而避免对空栈进行操作的未定义行为。
result数组在栈口取元素是否会覆盖原有数值
答案是不会因为result更新是在发现了一个更大的数值弹出的时候才会更新。
例如4 3 2这个例子遍历两遍得到的是4 3 2 4 3 2实际上后面那一组4 3 2的下标还是0 1 2数组下标是没有扩展的。
但是遍历前面这一组4 3 2的时候因为单调递减所以全部入栈栈内为2 3 4遍历第二遍的时候遇到了4栈内的2 3才被弹出相当于result[1]和[2]此时更新。但是到了后面3 2继续入栈到最后2 3 4都留在了栈里面不会被弹出因此也不可能导致result的值被覆盖
再例如2 3 4的例子遍历两遍得到2 3 4 2 3 4第一遍的时候result就已经被填满result[0]3,result[1]4,result[2]-1。到了遍历第二遍的时候此时栈内只有4第二次遍历时2入栈之后3再入栈会弹出2相当于result[0]仍然3同理result[1]仍然4。即使是result的值覆盖了结果依旧是不变的。
