185、【栈与队列】leetcode ——496. 下一个更大元素 I：单调栈-哈希表（C++版本）

news/2024/4/19 23:19:05/文章来源:https://blog.csdn.net/qq_41094332/article/details/129251778

题目描述

在这里插入图片描述

原题链接：496. 下一个更大元素 I

解题思路

本题与 739. 每日温度的区别在于，需要先通过让nums1与nums2判定出为想等元素后，再去找nums2中更大的数。

因此，第一步需要找到想等数，第二步需要找到大于的数。

对于第一步，我们可以用Hash表完成nums1与nums2中想等元素的映射关系，存储nums1中下标，采用空间换时间的方式，避免两重for循环。

对于第二步，就采用和每日温度相同的单调栈方式，维持一个从栈底到栈顶的递减栈。当遇到nums1与nums2中想等元素时，就记录答案。如果没有遇到就进行正常的入栈，出栈操作。

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {int n1 = nums1.size(), n2 = nums2.size();        vector<int> res(n1, -1);        unordered_map<int, int> umap;for(int i = 0; i < n1; i++)     umap[nums1[i]] = i;stack<int> st;                st.push(0);        for(int i = 1; i < n2; i++) {while(!st.empty() && nums2[st.top()] < nums2[i]) {if(umap.count(nums2[st.top()]) > 0) {int index = umap[nums2[st.top()]];res[index] = nums2[i];}st.pop();}st.push(i);}return res;}
};