给定一个可能含有重复值的数组 arr,找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。位置信息包括:两个数字 L 和 R,如果不存在,则值为 -1,下标从 0 开始。-笔试面试资料
这是qklbishe.com第6112 篇笔试面试资料
提供答案分析,通过本文《给定一个可能含有重复值的数组 arr,找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。位置信息包括:两个数字 L 和 R,如果不存在,则值为 -1,下标从 0 开始。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。
答案:
给定一个可能含有重复值的数组 arr,找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。位置信息包括:两个数字 L 和 R,如果不存在,则值为 -1,下标从 0 开始。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums intvector * @return intvector<vector<>> */ vector<vector<int> > foundMonotoneStack(vector<int>& nums) { // write code here vector<vector<int>>ans(nums.size(),vector<int>(2)); int stack[1000]={0}; int top = 0; //left ans[0][0] = -1; stack[top++] = 0; for(int i = 1; i < nums.size(); i++) { while(top != 0){ if(nums[i] > nums[stack[top-1]]){ ans[i][0] = stack[top-1]; stack[top++] = i; break; }else{ top--; } } if(top == 0){ stack[top++] = i; ans[i][0] = -1; } } //right ans[nums.size()-1][1] = -1; top=0; stack[top++] = nums.size()-1; for(int i = nums.size()-1; i >= 0; i--) { while(top != 0){ if(nums[i] > nums[stack[top-1]]){ ans[i][1] = stack[top-1]; stack[top++] = i; break; }else{ top--; } } if(top == 0){ stack[top++] = i; ans[i][1] = -1; } } return ans; } };
L值,第一个为-1,并将第一个元素下标进栈,对于后续每个元素ai,都与栈顶下标对应的的元素比较,如果栈顶下标元素小,则ai的L值为栈顶下标,并将ai下标进栈,否则,出栈继续比较直到有L值或者栈空,栈空则说明左边没有比ai小的元素,ai的L值为-1,ai下标进栈。
R值同理,从右往左遍历。
今天 00:52:44 回复(0)
文章部分来自互联网,侵权联系删除
www.qklbishe.com
区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站部分资料来自网络,侵权联系删除!资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 给定一个可能含有重复值的数组 arr,找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。位置信息包括:两个数字 L 和 R,如果不存在,则值为 -1,下标从 0 开始。-笔试面试资料
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 给定一个可能含有重复值的数组 arr,找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。位置信息包括:两个数字 L 和 R,如果不存在,则值为 -1,下标从 0 开始。-笔试面试资料