数组元素右边第一个比它大的数

素颜马尾好姑娘i 2023-02-28 04:16 94阅读 0赞

题目描述　　
给定一个无序的正整数数组, 找出数组中每个元素右边第一个比它大的数（若没有，则返回-1）
思路
将数组首元素的下标入栈从下标为1的元素开始遍历数组假设当前遍历到的第i个元素是x,若x大于栈顶下标对应的元素,那么这个栈顶下标对应元素的右边第一个比它大的数就是x,将栈顶下标出栈，然后继续处理剩下的元素，直到栈为空或者不再大于栈顶下标对应的元素如果当前遍历到的数组元素不大于栈顶下标对应的数组元素, 那就直接入栈
代码实现

  1. vector<int> FindFirstBigNum(vector<int>& v){
  3.  int len = v.size();
  4.  vector<int> res(len, -1);
  5.  if(len == 0){
  7.   return res;
  8.  }
  9.  stack<int> st;
  10.  st.push(0);
  11.  for(int i = 1; i < len; i++){
  13.   while(!st.empty() && v[i] > v[st.top()]){
  15.    res[st.top()] = v[i];
  16.    st.pop();
  17.   }
  18.   st.push(i);
  19.  }
  20.  return res;
  21. }

欢迎加入每日一题，每天分享一道高频面试题。
在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，94人围观）

还没有评论，来说两句吧...

相关阅读