FXTi's blog
0%

next-greater-element-i

Posted on Edited on

Next Greater Element I – LeetCode 496

Problem

Description

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1’s elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
        vector<int> res(findNums.size());
        for (int i = 0; i < findNums.size(); ++i) {
            int j = 0, k = 0;
            for (; j < nums.size(); ++j) {
                if (nums[j] == findNums[i]) break;
            }
            for (k = j + 1; k < nums.size(); ++k) {
                if (nums[k] > nums[j]) {
                    res[i] = nums[k];
                    break;
                }
            }
            if (k == nums.size()) res[i] = -1;
        }
        return res;
    }
};

思路

简单的查找到位置之后向后匹配。时间复杂度$O(n^{2})$，空间复杂度$O(1)$。
耗时$16$ ms，排名$71.16\%$

Better

思路

提前对nums数组生成一张表，存储着对应数字的下一个较大值位置。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$12$ ms，排名$35.25\%$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
        vector<int> res;
        stack<int> st;
        unordered_map<int, int> m;
        for (int num : nums) {
            while (!st.empty() && st.top() < num) {
                m[st.top()] = num; st.pop();
            }
            st.push(num);
        }
        for (int num : findNums) {
            res.push_back(m.count(num) ? m[num] : -1);
        }        
        return res;
    }
};