배열의 다음 큰 요소 찾기

Question

배열이 주어지면 모든 요소에 대해 주어진 요소의 오른쪽에서 현재 요소보다 큰 가장 작은 요소를 찾아야합니다.

수학적 배열 A의 모든 인덱스 i를 들어 , 난이 무력 솔루션은 O(n^2) 될 때마다 인덱스 i

에 대한 j을 찾을 필요가 인덱스 j 등이

A[j] > A[i] 
j > i 
A[j] - A[i] is minimum 

찾을 필요 나는 더 잘하기를 바라고 있습니다. 나는 O(n log n) 해결책이 자기 균형을 잡는 BST를 사용하여 가능하다고 생각하고 있습니다. 그러나 그것은 꽤 복잡한 것처럼 보입니다. 또한 O(n) 솔루션이 필요합니다.

이 문제의 해결책은 있습니까? O(n) 하한이 O(n log n)이라는 증거가 있습니까? O (nlogn)의

Answer 1

증명 하한 (비교 기반 알고리즘)은

우리가 O (N)이 작업을 수행하는 것 인 비교 - 기반의 알고리즘이 있다고 가정하자. 그것은 각 지수에 대한 것이고, 우리는 그 오른쪽에있는 더 큰 요소 (즉, R [i])를 가지고 있습니다.

마찬가지로 반전 된 입력 배열에서이 알고리즘을 실행 한 다음 결과를 반대로 할 수 있습니다. 각 색인에 대해 우리는 왼쪽에 즉각적으로 더 큰 요소를 가지고 있습니다 (L [i]).

이것은 O (n)에서 각 요소에 대해 배열 = min (R [i], L [i])에서 더 큰 요소가 있음을 의미합니다.

이제이 정보를 사용하여 배열을 정렬 할 수 있습니다.

배열에서 최소 요소를 찾습니다. 그것의 후계자 (즉시 큰 요소), 그 후계자의 후계자 등을 찾으십시오. 따라서 전체 배열을 정렬 된 순서로 얻었을 것입니다.

오직 비교 (모순)를 사용하여 O (n)의 배열을 정렬했습니다.

O (nlogn) 알고리즘 :
시작 어레이의 오른쪽 균형 BST 건물. 노드는 값과 각 인덱스를 포함합니다.

그런 다음 새로운 요소가 발견되면이를 BST에 삽입하면 가장 가까운 큰 색인/값이 생성됩니다.