185、【栈与队列】leetcode ——496. 下一个更大元素 I:单调栈-哈希表(C++版本)
2023-09-11 14:20:01 时间
题目描述
原题链接: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;
}
};
参考文章:496.下一个更大元素 I
相关文章
- C++多位整形数据相乘的代码
- C++编程兵书
- “Unable to find an entry point named [function] in dll” (c++ to c# type conversion)
- C++ 内联函数
- 托管C++线程锁实现 c++11线程池
- C++程序设计:原理与实践(进阶篇)15.8 调整vector类达到STL版本的功能
- 【C++】cmake初次编译-HelloWorld
- [C/CPP系列知识] 那些程序C语言可以编译通过但C++无法编译成功 Write a C program that won’t compile in C++
- 《C++面向对象高效编程(第2版)》——2.10 抽象数据类型—栈的实现
- Swift 基础100问之 02 在Swift中如何实现C/C++中的#ifdef功能 编译器预处理
- C++中的容器
- 163、【动态规划】leetcode ——198. 打家劫舍(C++版本)
- 161、【动态规划】leetcode ——139. 单词拆分:回溯法+动态规划(C++版本)
- 157、【动态规划】leetcode ——377. 组合总和 Ⅳ:二维数组+一维滚动数组(C++版本)
- 137、【贪心算法】leetcode ——406. 根据身高重建队列(多维度贪心)(C++版本)
- 117、【回溯算法】leetcode ——39. 组合总和:回溯法+剪枝优化(C++版本)
- 115、【回溯算法】leetcode ——216.组合总和III:回溯法+剪枝优化(C++版本)
- 109、【树与二叉树】leetcode ——701. 二叉搜索树中的插入操作:递归法+双指针迭代法(C++版本)
- 98、【树与二叉树】leetcode ——112. 路径总和:5行精简代码回溯法[带剪枝]+迭代法(C++版本)
- 73、【数组】leetcode——15. 三数之和(C++/Python版本)
- 65、【链表】leetcode——707. 设计链表(C++、Python版本)
- C++平均数1