下一个更大的元素I
和 739 完全一样
- 739是找每一个点的右边第一个大于点
- 该题是找部分点（num1）的右边第一个最大点
具体步骤
- 用map记录num1出现的点
- 然后和739一样找每一个右边第一个最大值
- 找到后判断该点是否是num1里面的，是就保存，不是就放弃
- 此处和739不同，739找到就保存
class Solution { public: vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { vector<int> result(nums1.size(),-1); stack<int> st; unordered_map<int,int> umap; for(int i=0 ; i<nums1.size(); i++) { umap[nums1[i]] = i; } // for(auto it:umap) cout<<it.first<<' '<<it.second<<endl; st.push(0); for(int i=1 ;i<nums2.size();i++) { while(st.empty()==0 && nums2[i] > nums2[st.top()]) { if(umap.count(nums2[st.top()]) > 0 ) { int index = umap[nums2[st.top()]]; result[index] = nums2[i]; } st.pop(); } st.push(i); } return result; } };
二刷
class Solution { public: vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { vector<int> result(nums1.size() , -1); unordered_map<int ,int> my_map; stack<int> my_stack; for(int i=0 ; i<nums1.size() ;i++) my_map[nums1[i]] = i; my_stack.push(0); for(int j=1; j<nums2.size() ;j++ ) { while(my_stack.size() != 0 && nums2[j] > nums2[my_stack.top()] ) { auto it = my_map.find(nums2[my_stack.top()]); if(it != my_map.end()) { result[it->second] = nums2[j]; } my_stack.pop(); } my_stack.push(j); } return result; } };
