单调栈
解题思路
由于 nums1 是 nums2 的子集，要求出 nums1 在 nums2 中下一个更大元素，直接求出 nums2 每个元素的下一个更大元素，再通过 hash 映射求出 nums1 在 nums2 中下一个更大元素；
hash 的 key 和 value 是元都是元素；
维护一个单调递减栈，每个元素都与栈顶元素比较，比栈顶元素大则出栈并更新 hash；
复杂度
-
时间复杂度：
O(m + n)；- 其中 n 是 nums2 的长度，需要遍历 nums2 以计算 nums2 中每个元素右边的第一个更大的值；
- 其中 m 是 nums1 的长度，需要遍历 nums1 以生成查询结果；
-
空间复杂度：
O(n)，用于存储哈希表；
代码实现
var nextGreaterElement = function (nums1, nums2) {
// 1. 声明一个 hash 表、单调栈、结果数组
const map = new Map(), stack = [], res = new Array(nums1.length).fill(-1);
// 2. 找到所有存在下一个更大的元素，放入 map 中，key：栈顶元素，value：当前元素
nums2.forEach(item => {
while (stack.length && item > stack[stack.length - 1]) {
map.set(stack.pop(), item);
};
stack.push(item);
});
// 3. 遍历 nums1 将结果推入 res 中
nums1.forEach((item, inx) => {
res[inx] = map.get(item) || -1;
});
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 700. 二叉搜索树中的搜索
上一篇
评论
