#include "s0496_next_greater_element_i.hpp" // 因为题干假设 nums1 中的元素全部在 nums2 中出现过, // 因此可以用常规的单调栈来处理 nums2 ,只不过在更新 ans // 的时候需要判断一下这个元素是否是 nums1 中的元素 vector S0496::nextGreaterElement(vector& nums1, vector& nums2) { int len1 = nums1.size(); int len2 = nums2.size(); if (len1 == 0) { return vector {}; } else if (len1 == 1) { return vector {-1}; } vector ans(len1, -1); // 先用哈希表来存储 nums1 中出现过的元素 // key 为元素的值,value 为元素的下标 unordered_map map; for (int i{0}; i < len1; ++i) { map[nums1[i]] = i; } // 开始遍历 nums2 stack s; for (int i{0}; i < len2; ++i) { // 如果栈为空则入栈并 continue if (s.empty()) { s.push(i); continue; } // 循环弹出,不是 if 弹出 while (nums2[i] > nums2[s.top()]) { // 如果元素存在于 nums1 中,则更新 ans if (map.count(nums2[s.top()]) > 0) { ans[map[nums2[s.top()]]] = nums2[i]; } s.pop(); // 栈为空则结束循环 if (s.empty()) { break; } } s.push(i); } return ans; }