В несортированном массиве мы должны заменить каждый элемент на первый элемент справа, который больше, чем текущий элемент. Если ни один из элементов справа больше, его следует заменить на -1.
Пример:
3 1 2 5 9 4 8 should be converted to
5 2 5 9 -1 8 -1
Я могу представить себе тривиальное решение, где мы проверяем каждый элемент со всем массивом, который является решением Ο (n²). Есть ли лучший способ сделать это?
Основная идея - обработать массив в обратном порядке (справа налево). Мы делаем несколько замечаний:
A[k] ≤ A[j], то мы вызываем элемент k неуместным, потому что он никогда не будет результатом для любого из элементов 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) не будут иметь элемент, отличный от элемента массива i.e. 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.
Поскольку у массива нет какого-либо элемента, просто не скажите, что в стеке говорят, что для всех элементов внутри массива не имеет большего элемента i.e. -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);
}
}