LeetCode 496 Next Greater Element I
概述
https://leetcode.com/problems/next-greater-element-i/
对于这种要运行多次的算法，我们需要建立一个数据结构来快速查询。
直接法
每次直接遍历，时间复杂度 O(mn)，m 和 n 分别是两个数组的个数。
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
vector<int> res;
for (auto i : nums1) {
int t = -1;
int found = false;
for (auto j : nums2) {
if (!found && j == i) found = true;
if (found && j > i) {
t = j;
break;
}
}
res.push_back(t);
}
return res;
}
};
基于单调栈的解法
https://labuladong.gitee.io/algo/2/20/51/
对于一个元素的下一个较大值，其答案必然仅存在其后面的元素中，因此我们应当反向遍历
然后我们需要维护一个数据结构用来存储有用的遍历过的值，新值加入后，那些没其大的旧值就可以淘汰掉了，因为其必然被挡住。
所以我们需要维护一个单调栈。
由于每个元素最多 push 一次，所以 while 循环最多运行 n 次，所以是 O(n) 的时间复杂度，n 为 num2 元素个数。
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> cache;
stack<int> s;
for (int i = nums2.size() - 1; i >= 0; i --) {
while (!s.empty() && s.top() <= nums2[i]) {
s.pop();
}
if (!s.empty()) {
cache[nums2[i]] = s.top();
}
s.push(nums2[i]);
}
vector<int> ans(nums1.size() , -1);
for (int i = 0; i < nums1.size(); i ++) {
if (cache.count(nums1[i])) ans[i] = cache[nums1[i]];
}
return ans;
}
};