欢迎光临
我们一直在努力

计算机给定一个可能含有重复值的数组 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 开始。

给定一个可能含有重复值的数组 arr,找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。位置信息包括:两个数字 L 和 R,如果不存在,则值为 -1,下标从 0 开始。-笔试面试资料 cyan!
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

赞(0)
未经允许不得转载: 京大飞辅助网程序员面试-区块链javago面经 » 计算机给定一个可能含有重复值的数组 arr,找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。位置信息包括:两个数字 L 和 R,如果不存在,则值为 -1,下标从 0 开始。-笔试面试资料

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址