57-下一个更大元素Ⅰ

自己的做法

算法思想

将nums2的所有元素添加到一个map集合中，key为各元素的值，value为该元素的索引。

然后遍历nums1数组，对于每一个元素，从map中找到与该元素的值相等的key对应的value，即当前元素对应nums2的元素的索引。然后从该索引开始遍历，如果存在比该元素大的，就加到res数组，否则就添加-1。

算法实现

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        unordered_map<int, int> index;
        for(int i = 0; i < nums2.size(); i++) {
            index[nums2[i]] = i;
        }
        for(int i = 0; i < nums1.size(); i++) {
            int j;
            for(j = index[nums1[i]] + 1; j < nums2.size(); j++) {
                if(nums2[j] > nums1[i]) {
                    res.push_back(nums2[j]);
                    break;
                }
            }
            if(j == nums2.size()) {
                res.push_back(-1);
            }
        }
        return res;
    }
};

性能分析

时间复杂度：最坏情况，nums2是一个由大到小排列的数组，那么对于在num1中的每个元素，都会从nums2中的对应位置遍历到末尾。时间复杂度为$O(mn)$，m为nums1的长度，n为nums2的长度。

空间复杂度：$O(n)$。使用了一个map集合来存放nums2中元素，结果数组res不计入空间复杂度。

参考做法

算法思想

使用单调栈来做。

使用哈希表来存放nums2中每个元素和它的下一个更大元素。

单调栈：

依次遍历数组，设当前元素为t，如果栈顶元素大于t，那么就将t入栈；如果栈顶元素小于t，那么栈顶元素的下一个更大元素就是t，出栈，并添加到哈希表中，继续判断当前栈顶元素是否小于t，如是，则执行上一步，循环执行，直到当前栈顶元素大于t。然后添加t到栈中，继续判断。直到遍历结束。

可以发现，维护的栈保证了单调性，栈中的元素从栈顶到栈底是递增的。

注：最后一步，7大于4和6，应该是依次出栈。

算法实现

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

性能分析

时间复杂度：两个数组各遍历了一遍，$O(m + n)$。

空间复杂度：$O(n)$，遍历数组2需要使用栈和哈希表。