题解48 | #下一个更大的数(二)#

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型vector
     */
    vector<int> nextBigger(vector<int>& nums) {
        // write code here
        vector<int> ans(nums.size(), -1);
        int n = nums.size();

        stack<int> sMax;

        for (int i = 0; i < n; i++) {
            while (!sMax.empty() && nums[i] > nums[sMax.top()] ) {
                int now = sMax.top();
                sMax.pop();
                ans[now] = nums[i];
            }
            sMax.push(i);
        }

        for (int i = 0; i < n; i++) {
            while (!sMax.empty() && nums[i] > nums[sMax.top()] ) {
                int now = sMax.top();
                sMax.pop();
                ans[now] = nums[i];
            }

        }

        return ans;
    }
};

该算法的基本思想：

使用一个栈sMax来保存数组元素的下标，栈中的元素按照从小到大的顺序排列。遍历数组元素，如果当前元素大于栈顶元素对应的数组元素，则弹出栈顶元素，并将其对应的数组元素更新为当前元素。最后栈中剩余的元素对应的数组元素无法找到比其大的元素，将其更新为-1。

这段代码中有两个for循环的原因是为了处理两种情况。

第一个for循环是处理数组中的元素，从左到右遍历数组。在遍历过程中，使用一个栈sMax来保存当前位置之前的较大元素的索引。如果当前元素比栈顶元素对应的元素大，则将栈顶元素出栈，并将其对应的ans数组位置上的值更新为当前元素。这样可以保证ans数组中存储的是当前位置之后的下一个较大元素。

第二个for循环是处理剩余的栈中的元素。由于栈中的元素是递减的，所以剩余的元素没有下一个较大元素。因此，将这些元素对应的ans数组位置上的值保持为-1。

通过这两个for循环，可以得到每个元素的下一个较大元素。

时间复杂度：

O(n)，其中n为数组元素的个数。遍历数组需要O(n)的时间，每个元素最多入栈和出栈一次。

空间复杂度：

O(n)，需要使用一个栈来保存数组元素的下标，栈的大小最大为n。