496下一个更大的数

下面是题目

下面是题目给出的模板

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {

    }
};

先讲讲我拿到这道题的思路

• 像我这种基本数据结构都不太会用的垃圾，拿到这种题最先想到的就是BF，但是我没想到自己得BF功底都这么差，写完以后 运行时间达到了惊人的100ms和27MB，着实显示了我的无能！

其实BF也可以很好看很简单的！我的解法过于丑陋，就不在这展示了

//这里想把vector遍历拓展一下
/*
	一般我们遍历vector容器都会使用方括号或者迭代器，但是这里出现了一种新方法
	那就是for(int n : v ) 其中v是vector容器
	这句话等价于：for(int i=0;i<v.size();i++)
				{
					int i = v[n];
				}
	所以说 n 就是等于把所有vector中的元素都遍历一遍 相当于for/of(js语法)
	后一种常用的则是把所有 vector中的索引都遍历一遍	相当于for/in(js语法)

*/
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        for(int n: nums1){
            int i = 0;
            while(nums2[i] != n) i++;
            //每次都找到nums1中的元素在nums2中的索引
            i++;
            //从这个索引开始向后遍历
            for(;i<nums2.size();i++){
                if(nums2[i] > n){
                    //每当找到比nums1种元素大的数边存储
                    res.push_back(nums2[i]);
                    break;
                }
            }
            //那么，如果全部遍历完成以后，还是没有，那么这个数后面没有更大的了
            if(i == nums2.size()) res.push_back(-1);
        }
        return res;
    }
};

当然，用栈和无序图来存储也是比较美观的

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        unordered_map<int, int> mp;
        stack<int> sk;
//同样用到了for( : )语法
        for(int n: nums2){
//这时候如果栈是非空的，并且栈顶元素是小于当前的n
//那么我们就在无序图中以key=栈顶，val= n 存储，这时候其实n就是栈顶所对应的更大的数
            while(!sk.empty() && sk.top() < n){
                mp[sk.top()] = n;
                sk.pop();
            }
//否则，我们把n入栈 
            sk.push(n);
        }
//那么如果遍历结束以后，栈非空，那么说明说明栈里的元素没有匹配的n
        while(!sk.empty()){
            mp[sk.top()] = -1;
            sk.pop();
        }
//最后，我们把无序map中所有的val值放入vector并返回
        for(int n: nums1){
            res.push_back(mp[n]);
        }
        return res;        
    }
};