力扣-动态规划-496 下一个更大的元素Ⅰ

思绪和时间复杂度

• 思绪：标题中的意思为是值类似的情况下的右边第一个最大的元素，以是直接在nums2中探求下一个最大元素即可，要用map记载一下下标和值，在nums中找到下一个最大值，还要确认当前比力的值是否在num1中
  
• 时间复杂度： 
  
        
  

代码

2. class Solution {
3. public:
4.     vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
5.         vector<int> res(nums1.size(), -1);
6.         // 遍历nums2，找到nums2的每一个元素在右边第一个大的元素，然后利用元素值定位nums1，找到下标
7.         unordered_map<int, int> ump;
8.         
9.         for(int i = 0; i < nums1.size(); i++){
10.             ump[nums1[i]] = i;
11.         }
13.         stack<int> st;
14.         st.push(0);
15.         for(int i = 1; i < nums2.size(); i++){
16.             if(nums2[i] > nums2[st.top()] ){
17.                 while(!st.empty() && nums2[i] > nums2[st.top()] ){
18.                     if(ump.count(nums2[st.top()]) >= 1){
19.                         int index = ump[nums2[st.top()]];
20.                         res[index] = nums2[i];
21.                     }
22.                     st.pop();
23.                 }
24.                 st.push(i);
25.             }else{
26.                 st.push(i);
27.             }
28.         }
30.         return res;
31.     }
32. };

复制代码