下一个更大元素

给你一个下标从?0?开始的非负整数数组?nums?。对于?nums?中每一个整数，你必须找到对应元素的?第二大?整数。

如果?nums[j]?满足以下条件，那么我们称它为?nums[i]?的?第二大?整数：

• j > i
• nums[j] > nums[i]
• 恰好存在?一个?k?满足?i < k < j?且?nums[k] > nums[i]?。

如果不存在?nums[j]?，那么第二大整数为?-1?。

• 比方说，数组?[1, 2, 4, 3]?中，1?的第二大整数是?4?，2?的第二大整数是?3?，3?和?4?的第二大整数是?-1?。

请你返回一个整数数组?answer?，其中?answer[i]是?nums[i]?的第二大整数。

样例范围：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

?问题分析：

数组给规模限制使得该问题的复杂度不能达到O(n2)。

题目说的第二大的数，假设当前元素为i，第二大元素的位置为j，也就是说在i到j中有且只有一个数比i大。也就是说我们只需要用一个数组存储到当前元素已经有一个比他大的数。第二次碰到就是它的答案。

我们用res来表示答案数组。另外设一个st1来存储遍历到当前的所有比当前元素小的元素下标，当当前元素大于栈中的元素的时候，也就是说对于st1中的数据，存在第一个比它大的数，那么只需要在后面再找一个比他大的数，那个数就是第二大数。设st2来存储st1中排出的数，也就是说st2中的元素只需要再一次找到一个比他大的数就好了，到当前元素，就把st2中所有小于当前元素的就得到了答案。

代码展示：

class Solution {
public:
    vector<int> secondGreaterElement(vector<int> &nums) {
        int n = nums.size();
        vector<int> res(n, -1);
        vector<int> st1;
        vector<int> st2;
        for (int i = 0; i < n; ++i) {
            int v = nums[i];
            while (!st2.empty() && nums[st2.back()] < v) {
                res[st2.back()] = v;
                st2.pop_back();
            }
            int pos = st1.size() - 1;
            while (pos >= 0 && nums[st1[pos]] < v) {
                --pos;
            }
            st2.insert(st2.end(), st1.begin() + (pos + 1), st1.end());
            st1.resize(pos + 1);
            st1.push_back(i);
        }
        return res;
    }
};

代码分析：

1.若该 st2非空且栈顶元素小于当前遍历的元素时，说明当前元素为栈顶元素的第二大的整数，将栈顶元素出栈，并更新结果数组。重复该操作直至 st2为空或者栈顶元素大于等于当前遍历元素。
2.若 st1非空且栈顶元素对应的值小于当前遍历元素，则说明找到了栈顶元素的下一个更大的数字，将栈顶元素出栈。重复执行该操作直至 st1为空或者栈顶元素大于等于当前遍历元素。然后我们将出栈的元素按照在栈 st1中的顺序加入栈 st2中。
3.将当前元素的下标压入栈 st1中。

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)