刷代随有感(134):单调栈——下一个更大元素I（难点涉及哈希表与单调栈的结合)

单调栈处理的是下标！

题干：

代码：

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {stack<int>ddst;unordered_map<int,int>umap;vector<int>res(nums1.size(), -1);if(nums1.size() == 0)return res;for(int i = 0; i < nums1.size(); i++){umap[nums1[i]] = i;}ddst.push(0);for(int i = 1; i < nums2.size(); i++){if(nums2[i] <= nums2[ddst.top()]) ddst.push(i);else{while(!ddst.empty() && nums2[i] > nums2[ddst.top()]){//结果记录if(umap.count(nums2[ddst.top()]) > 0){int index = umap[nums2[ddst.top()]];//获取此数组2元素(栈顶)在数组1中下标值res[index] = nums2[i];//将遍历到的(不是栈顶)放入res中}ddst.pop();//记录完成后弹出(持续)}ddst.push(i);}}return res;}
};

哈希表的思想：在数组2里找元素而在数组1里面确定，涉及映射关系考虑哈希map。