在未排序的数组中，我们必须用右边的第一个元素替换每个元素，该元素大于当前元素。如果右边的元素都不大，那么它应该替换为 -1。
例：
3 1 2 5 9 4 8 should be converted to
5 2 5 9 -1 8 -1
我可以想到一个简单的解决方案，我们用整个数组检查每个元素 Ο（N²） 解。有一个更好的方法吗？
在未排序的数组中，我们必须用右边的第一个元素替换每个元素，该元素大于当前元素。如果右边的元素都不大，那么它应该替换为 -1。
例：
3 1 2 5 9 4 8 should be converted to
5 2 5 9 -1 8 -1
我可以想到一个简单的解决方案，我们用整个数组检查每个元素 Ο（N²） 解。有一个更好的方法吗？
主要思想是以相反的顺序（从右到左）处理数组。我们做了一些观察：
A[k] ≤ A[j]，然后我们称之为元素 ķ 无关紧要，因为它永远不会是任何元素的结果 1,2，...，kA[i+1..n-1]。在您的示例中，相关元素的序列将从右到左：
[]
[8]
[4,8]
[9]
[5,9]
[2,5,9]
[1,5,9]
它看起来像一个堆栈，我们确实可以使用堆栈来在迭代之间维护这个序列。
处理新元素时，我们首先需要找到数组元素的结果。观察结果是结果是堆栈中最顶层的元素 不 由新元素无效。因此，我们可以从堆栈中弹出所有已变得无关紧要的元素。那么最重要的是我们的结果。然后我们可以推送新元素，因为它与我们的定义相关。
stack = []
A = [3, 1, 2, 5, 9, 4, 8]
result = [-1]*len(A)
for i := len(A) - 1 to 0:
# remove all elements made irrelevant by A[i]
while not stack.empty() && stack.top() <= A[i]:
stack.pop()
# now the top of the stack is the result for index i
if not stack.empty():
R[i] = stack.top()
# push the new element on the stack. The stack will still contain all relevant
# elements in increasing order from top to bottom
stack.push(A[i])
迭代的循环不变量 i 是“stack 包含索引右侧相关元素的子序列 i“。很容易验证并暗示该算法的正确性。
每个元素最多被推送和弹出一次，因此我们的总运行时间为 Ο（n）的。
你可以使用堆栈，时间复杂度是 O(N)。
algo:
从左侧开始向右移动。当你从数组中选择一个元素（比方说x）时，弹出堆栈直到堆栈中的元素（比方说y）的元素大于数组元素，即x> y。比推动元素即x叠加。
例如 {40,50,11,32,55,68,75} 。这里 s 是堆栈。
40，因为s是空的推它。 s: 40
50，因为s.peek（）<50所以pop 40（40的元素是50）比推50。 s: 50
下一个更高的元素是40-50。
11，s.peek（）> 11所以推11。 s: 50, 11
32，s.peek（）<32，所以弹出元素，现在它是50，大于32因此推32。 s: 50 ,32
下一个更高的元素是11 - 32。
55，s.peek（）<55，因此弹出元素，即32比弹出下一个以及50 <55，而不是55。 s: 55。
下一个更高的元素是32 - 55。
下一个更高的元素50 - 55。
68，s.peek（）<68所以弹出它并推68。 s: 68
75，s.peek（）<75所以弹出它并推75 s:75。
下一个更高的元素是68-75。
由于数组没有任何元素，因此不会弹出堆栈，表示数组中的所有元素都没有更大的元素，即-1。
下一个更高的元素是75 - -1。
代码中的算法相同：
public static void fun(int[] a) {
Stack<Integer> s = new Stack<Integer>();
s.push(a[0]);
for (int i = 1; i < a.length; i++) {
if (s.peek() != null) {
while (true) {
if (s.peek() == null || s.peek() > a[i]) {
break;
}
System.out.println(s.pop() + ":" + a[i]);
}
}
s.push(a[i]);
}
while (s.peek() != null) {
System.out.println(s.pop() + ":" + -1);
}
}