간격이 A [i-j]라고하면 RMQ를 사용하여 간격 A [i-j] 사이의 최소값을 쉽게 찾을 수 있습니다. 이제 조건을 반전 시키려고합니다. 최소값이 주어지면이 숫자가 최소 숫자로 포함 된 간격 (최대 길이)을 찾습니다. 이진 검색을 사용하여 구현하려고했지만 그렇게하지 못했습니다. 이 문제에 접근하는 방법을 설명해주십시오. 고맙습니다 . !! !!범위 최소 쿼리로 이진 검색을 구현하는 방법은 무엇입니까?
다음은 선형 시간에 배열의 각 요소에서 가장 가까운 작은 숫자를 계산하는 간단한 알고리즘입니다. 아이디어는 쌍 (요소, 위치)의 스택을 유지하고 더 이상 유용하지 않을 때 요소를 튀어 나오게하는 것입니다. 의사 코드 :
stack = new Stack<Pair>() // an empty stack of pairs(element, position)
leftSmaller = new int[n] // an array to store the answer
fill(leftSmaller, -1)
for (i = 0; i < n; i++) // n is the size of the given array
while (!stack.isEmpty() and stack.top().first >= array[i]) // pop the elements from the stack while they are larger the current element
stack.pop()
if (!stack.isEmpty()) // if there is a smaller element
leftSmaller[i] = stack.top().second // its position is the answer for the current position
stack.push(new Pair(array[i], i))
각 요소는 한 번만 스택에 푸시되고 최대 한 번 튀어 나오게됩니다. 그것이 시간 복잡성이 O(n) 인 이유입니다.
질문에 표시된 문제와 관련하여 어떤 관련이 있습니까? 배열의 각 위치에 대해 첫 번째 작은 요소를 왼쪽에 미리 계산할 수 있습니다.이 배열은 역순으로 배열에서이 알고리즘을 실행하여 오른쪽에있는 첫 번째 작은 요소입니다. i 위치에 대한 대답은 rightSmaller[i] - leftSmaller[i] - 1입니다. 배열의 각 위치에 대한 답을 알고 나면 원래 문제를 쉽게 풀 수 있습니다 (i 중에서 가장 좋은 답을 선택하십시오)
코드를 작성하지 않고, 그러나 그 문제에 접근하는 방법은 1) 배열에서 목표 값을 찾은 다음 2) 값이 목표보다 크고 3) 오른쪽에서 동일한 작업을 수행하면서 배열의 왼쪽으로 간격을 확장합니다 ... 바이너리 검색은 배열을 작업 순서대로 정렬해야하므로 (이 경우 간격을 찾는 것이 쉽지 않음) 정렬되지 않은 배열이 주어질 때 값에 대한 보장이 없기 때문에 이진 검색이 올바른 도구가 아닙니다. 두 점 사이에 ... – twalberg
"배열에서 왼쪽으로 간격을 확장하십시오". 배열이 {5,4,3,2,1}이되도록하십시오. 최소값은 1입니다.이 경우 Interval을 1로 확장하는 대신 효율적으로 왼쪽으로 트래버스하는 방법. – monsterspy