시퀀스 <code>a[1], a[2], a[3] .... a[n]</code>을 감안할 때 시퀀스

Question

에있는 모든 요소의 전신 찾기, 내가 모든 a[i]에 대한 찾을 수있다, a[j] 시퀀스 a[i - 1], a[i - 2], a[i - 3].... 등이 a[j] < a[i]의 첫 번째 요소는 요소 a[j]입니다.

다른 말로하면 a[j]은 a[j] < a[i]과 1<=j<i입니다. 그러나 이러한 요소가 여러 개인 경우 a[i]에 가장 가까운 요소를 선택해야합니다. 다음 순서로 예를 들면

:

2 6 5 8

난이 O(n^2) 쉽게 할 수있어 제

모두 6 및도 5, 및도 5의 출력 (2)이 , 그러나 이것을하는 더 효율적인 방법이 있습니까?

Answer 1

stack을 사용하여 O(n)에서 수행 할 수 있습니다.

a = your array 
d = a stack 
d.push(a[1]) 
for i = 2 to n do 
    while d.top > a[i] do 
    d.pop() 

    print d.top if it exists, else -1 
    d.push(a[i]) 

기본적으로, 우리는 분류 d을 유지하고 마지막 요소는 항상 a[i]보다 작은 있는지 확인합니다. 이 방법은 d의 마지막 요소는 항상 우리가 찾고있는 것입니다.

중첩 된 루프로 인해 선형 복잡성이 즉시 명확하지 않을 수 있지만 각 요소가 최대 1 회 스택을 벗어나지 않고 일정한 횟수만큼 스택에 들어가는 것을 관찰하십시오.