O (n)에서 주어진 배열의 각 부분 배열에 대한 가장 작은 정수의 모든 쌍을 찾으십니까?

Question

문제가 있습니다. 배열이 주어지면 가능한 모든 하위 배열에 대해 가장 작은 정수와 두 번째로 작은 정수를 찾습니다. 여기서 하위 배열은 원래 배열의 인접한 하위 집합입니다.

예를 들어 배열 A = [5, 6, 1, 2, 9, 3]을 생각해보십시오. 분명히 서브 어레이 크기는 적어도 2가 될 것이므로 총 (n) * (n + 1)/2 - n 서브 어레이가 있습니다. (크기 1의 총합에서 n 개의 서브 어레이를 뺍니다). 그것은 각각의 하위 배열을 검사하고 필요한 정수를 기록하는 직선적 인 O (n^2) 솔루션입니다. 하지만 스택을 사용하여 O (n)에서 수행 할 수 있다고 생각합니다. 하지만 나는 최적의 솔루션에 도달하기 위해 그것을 직관적으로 사용할 수 없습니다. 도움, 조언, 방향에 감사드립니다.

Answer 1

예 O (n)에서 수행 할 수 있습니다.이 아이디어는 question을 해결하는 데 사용됩니다.

For each int i in the array A 
    while stack is nonempty 
     // current min is stack.top() and A[i] 
     if i is less than the top of the stack, pop the stack 
     otherwise break the while loop 
    If stack is non empty 
     // current min is stack.top() and A[i] 
    push i onto stack 

기본 아이디어는 당신이 당신의 스택의 값 (B)을 가지고, 당신은 작은 값의 C가 발생할 경우, 다음에 b가 C의 오른쪽에 아무것도 최소 쌍을 형성 할 수 없다는 것입니다. 따라서 한 쌍의 (b, c) 쌍을 얻으면 b를 안전하게 처분 할 수 있습니다 (이미 가능한 쌍을 왼쪽에 처리했습니다). 내가 대답을 감사 드리며

는 online compiler