找到一個數組中每一個元素第一個比它大的元素

一、題目描述

        給定義個數組v,對于數組中每一個元素，找到其後面元素中第一個比它大的元素，并且記錄在數組v2中傳回。例如給定數組v = {1,3,6,-1,2},傳回v2={3,6,-1,2,-1}。（如果找不到，記為-1），并且要求時間複雜度應該為O(N)。

二、解題思路

        可能看到這道題，大家首先會想到對于數組中的元素一個一個去周遊，進而找到第一個比它大的元素，但是這種做法的時間複雜度應該為O（n**2）,是以不可采用此種方法。

        進一步去思考，發現可以利用堆棧去解決，如果對于目前元素v[i],發現v[i]+1 < v[i],此時不用再去比較v[i+2]與v[i]的關系，而是把i壓入堆棧中，去比較v[i+1]與v[i+2]的關系，一旦發現滿足後一個元素大于第一個元素的，便輸出。

vector<int> FindMax(vector<int> &num)
{
  int len = num.size();
if(len == 0) return {};
vector<int> res(len,-1);
stack<int>  notFound;
int i = 0;
while(i<len)
{
if(notFound.empty() || num[notFound.top()] > num[i])
{
    notFound.push(i++);
}
else
{
  res[notFound.top()] = num[i];

notFound.pop();
}

}
return res;

}