1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] ans = new int[nums.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                ans[stack.pop()] = nums[i];
            }
            stack.push(i);
        }
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                ans[stack.pop()] = nums[i];
            }
        }
        while (!stack.isEmpty()) {
            ans[stack.pop()] = -1;
        }
        return ans;
    }
}

第一遍把能成全的都成全了. 可能此时stack中还剩下一些index未被成全, 那么我们看看是否它们的左侧有能成全它们的数字吧. 于是我们第二次循环就不需要push, 看看能成全多少就成全多少. 最后如果stack中还有index, 那就说明这些index不能被成全, 给ans对应位置赋-1即可.

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