LeetCode 496 Next Greater Element I

标签: 设计数据结构 LeetCode 发布于:2022-02-11 13:17:13 编辑于:2022-02-11 13:17:44 浏览量:373

概述

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/