给定两个没有重复元素的数组munsSub
和numsAll
,其中numsSub
是numsAll
的子集。找到numsSub
中的每个元素在numsAll
中的下一个比其大的元素。比如,numsSub
中的一个元素x在numsAll
中的下一个比其大的元素是指,x在numsAll
中位置开始,下一个序号比其大值也比其大的第一个元素。如果不存在这个一个比其大的元素,则输出结果为-1。
示例:
numsSub = {4, 1, 2};
numsAll = {1, 3, 4, 2}; 结果为:{-1, 3, -1};numsSub = {4, 2, 9}
numsAll = {5, 4, 8, 2, 9, 7, 3}; 结果为:{8, 9, -1};
代码:
int main(int argc, char *argv[]) { int numsSub[] = {4, 1, 2}; int numsAll[] = {1, 3, 4, 2}; std::stack s; std::unordered_mapnextBigger; for (int i = 0; i < (sizeof(numsAll)/sizeof(numsAll[0])); ++i) { while(!s.empty() && numsAll[i] > s.top()) { nextBigger[s.top()] = numsAll[i]; s.pop(); } s.push(numsAll[i]); } int bigger = -1; for (int i = 0; i < (sizeof(numsSub)/sizeof(numsSub[0])); ++i) { auto it = nextBigger.find(numsSub[i]); if (it == nextBigger.end()) { bigger = -1; } else { bigger = it->second; } std::cout << numsSub[i] << " next bigger number is: " << bigger << std::endl; }}