谷歌NEXT program最后一题解法

索引按值排序，维护索引递增栈。时间复杂度O(nlogn)代码如下，顺便说一下，楼主给的答案少了一个.. def nextProgram(l:list): l = sorted(list(enumerate(l)), key=lambda x:x[1]) res = [-1] * len(l) stack = [] for i,e in l: while len(stack) > 0 and stack[-1] < i: index = stack.pop() res[index] = e stack.append(i) return res print(nextProgram([11,13,10,5,12,21,3])) #[12, 21, 12, 12, 21, -1, -1]

vector<int> findNext(vector<int> A, int n) {     // write code here     map<int, int> m;     vector<int> result(n, -1);     for(int i = n - 1; i >= 0; i --){         for(auto item : m){             if(item.first > A[i]){                 result[i] = item.first;                 break;             }         }         m.insert({A[i], 1});     }     return result; } 直接用STL自带的map(红黑树）就行了

可以对索引按值排序然后维护一个递减的栈，也可以直接用cpp和java里面内置的数据结构

vector<int> minCost(vector<int>& num) {     vector<int> ans;     map<int,int> m;     for(int i=num.size()-1;i>=0;i--){         map<int,int>::iterator it=m.lower_bound(num[i]+1);         if(it==m.end()){             ans.push_back(-1);         }         else{             ans.push_back(it->first);         }         m[num[i]]++;     }     reverse(ans.begin(),ans.end());     return ans; }