496. 下一个更大元素 I

自己的代码不贴了,像hamburger

一、正向递增栈+hashmap

 1 vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
 2     stack<int> use;
 3     unordered_map<int, int> map;
 4 
 5     for (int i = 0; i < nums2.size();++i)
 6     {
 7         if (use.empty()||nums2[i] < use.top())
 8         {
 9             use.push(nums2[i]);            
10         }
11         else
12         {
13             while (!use.empty()&&nums2[i] > use.top())
14             {
15                 map[use.top()] = nums2[i];
16                 use.pop();
17             }
18             use.push(nums2[i]);
19         }
20     }
21     while (!use.empty())
22     {
23         map[use.top()]= - 1;
24         use.pop();
25     }
26     vector<int> res;
27     for (auto e : nums1)
28     {
29         res.push_back(map[e]);
30     }
31     return res;
32 }

 

二、反向递增栈+hashmap

 1 vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
 2     stack<int> use;
 3     unordered_map<int, int> map;
 4     for (int i = nums2.size() - 1; i >= 0; --i)
 5     {
 6         if (use.empty())
 7         {
 8             use.push(nums2[i]);
 9             map[nums2[i]] = -1;
10         }
11         else if (use.top() > nums2[i])
12         {
13             map[nums2[i]] = use.top();
14             use.push(nums2[i]);
15         }
16         else 
17         {
18             while (!use.empty() && use.top() < nums2[i])
19             {
20                 use.pop();
21             }
22             if (!use.empty())
23             {
24                 map[nums2[i]] = use.top();
25                 use.push(nums2[i]);
26             }
27             else
28             {
29                 map[nums2[i]] = -1;
30                 use.push(nums2[i]);
31             }
32         }
33     }
34     vector<int> res;
35     for (auto e : nums1)
36     {
37         res.push_back(map[e]);
38     }
39     return res;
40 }

 

上一篇:chorme唤起Java开发的本地程序全采坑记


下一篇:496. Next Greater Element I