앨리스와 밥이 만날 수 있는 건물 찾기

2940. 앨리스와 밥이 만날 수 있는 건물 찾기

난이도:어려움

주제: 배열, 이진 검색, 스택, 이진 인덱스 트리, 세그먼트 트리, 힙(우선순위 큐), 단조 스택

양의 정수로 구성된 0-인덱스 배열 높이가 제공됩니다. 여기서 heights[i]는 i^번째 건물의 높이를 나타냅니다.

어떤 사람이 건물 i에 있으면 i < j 및 heights[i] < 높이[j].

queries[i] = [a_i, b_i]인 또 다른 배열 쿼리도 제공됩니다. i^번째 쿼리에서 Alice는 a_i 건물에 있고 Bob은 b_i 건물에 있습니다.

ans[i]가 i번째 쿼리에서 Alice와 Bob이 만날 수 있는 ^{가장 왼쪽 건물의 인덱스}인 배열 ans를 반환합니다. Alice와 Bob이 쿼리 i에서 공동 건물로 이동할 수 없는 경우 ans[i]를 -1로 설정합니다.

예 1:

• 입력: 높이 = [6,4,8,5,2,7], 쿼리 = [[0,1],[0,3],[2,4],[3,4] ,[2,2]]
• 출력: [2,5,-1,5,2]
• 설명: 첫 번째 쿼리에서는 heights[0] < 높이[2] 및 높이[1] < 높이[2].
  • 두 번째 쿼리에서 Alice와 Bob은 heights[0] < 높이[5] 및 높이[3] < 높이[5].
  • 세 번째 쿼리에서는 앨리스는 다른 건물로 이동할 수 없기 때문에 밥을 만날 수 없습니다.
  • 네 번째 쿼리에서 Alice와 Bob은 heights[3] < 높이[5] 및 높이[4] < 높이[5].
  • 다섯 번째 쿼리에서 Alice와 Bob은 이미 같은 건물에 있습니다.
  • ans[i] != -1의 경우 ans[i]가 Alice와 Bob이 만날 수 있는 가장 왼쪽 건물임을 알 수 있습니다.
  • ans[i] == -1의 경우, 앨리스와 밥이 만날 수 있는 건물이 없음을 알 수 있습니다.

예 2:

• 입력: 높이 = [5,3,8,2,6,1,4,6], 쿼리 = [[0,7],[3,5],[5,2],[ 3,0],[1,6]]
• 출력: [7,6,-1,4,6]
• 설명: 첫 번째 쿼리에서 heights[0] < 이므로 Alice는 Bob의 건물로 직접 이동할 수 있습니다. 높이[7].
  • 두 번째 쿼리에서 Alice와 Bob은 heights[3] < 높이[6] 및 높이[5] < 높이[6].
  • 세 번째 쿼리에서는 Bob이 다른 건물로 이동할 수 없기 때문에 Alice는 Bob을 만날 수 없습니다.
  • 네 번째 쿼리에서 Alice와 Bob은 heights[3] < 높이[4] 및 높이[0] < 높이[4].
  • 다섯 번째 쿼리에서는 heights[1] < 높이[6].
  • ans[i] != -1의 경우 ans[i]가 Alice와 Bob이 만날 수 있는 가장 왼쪽 건물임을 알 수 있습니다.
  • ans[i] == -1의 경우, 앨리스와 밥이 만날 수 있는 건물이 없음을 알 수 있습니다.

제약조건:

• 1 <= heights.length <= 5 * 10⁴
• 1 <= 높이[i] <= 10⁹
• 1 <= query.length <= 5 * 10⁴
• 쿼리[i] = [a_i, b_i]
• 0 <= a_i, b_i <= heights.length - 1

힌트:

1. 각 쿼리 [x, y]에 대해 x > y, x와 y를 바꿉니다. 이제 x

2. 각 쿼리 [x, y]에 대해 x == y 또는 heights[x] < heights[y]이면 x ≤ y이므로 답은 y입니다.
3. 그렇지 않으면 y < t 및 높이[x] < 높이[t]. heights[y] <= heights[x]이므로 heights[x] < 높이[t]는 충분조건입니다.
4. 각 쿼리에 대한 인덱스 t를 찾으려면 쿼리를 y의 내림차순으로 정렬하세요. 인덱스 t를 찾기 위해 이진 검색이 가능한 단조로운 스택을 유지하면서 쿼리를 반복합니다.

해결책:

문제는 시작 건물과 이동 규칙을 고려하여 앨리스와 밥이 만날 수 있는 가장 왼쪽 건물을 결정해야 합니다. 각 쿼리에는 건물 높이를 기준으로 만남의 장소를 찾는 것이 포함됩니다. 이는 이동에 대한 제약과 효율적인 계산의 필요성으로 인해 어려운 작업입니다.

핵심사항

1. 앨리스와 밥은 건물 높이가 현재 건물보다 엄격하게 높을 경우 다른 건물로 이동할 수 있습니다.
2. 각 쿼리에 대해 가장 왼쪽의 유효한 모임 장소를 찾거나 해당 건물이 없으면 -1을 반환합니다.
3. 제약조건으로 인해 순진한 O(n²) 접근 방식보다 더 나은 솔루션이 필요합니다.

접근방법

1. 관찰:

   • a == b인 경우 Alice와 Bob은 이미 같은 건물에 있습니다.
   • 높이[a] < heights[b], 밥의 건물이 만남의 장소입니다.
   • 그렇지 않으면 가장 작은 건물 지수 t > b 여기서:
     • 높이[a] < 높이[t]
     • heights[b] <= heights[t] (b는 이미 높이 비교에서 a보다 작기 때문에).

2. 단조 스택을 사용한 최적화:

   • 단조 스택은 Alice와 Bob이 이동할 수 있는 유효한 건물을 효율적으로 추적하는 데 도움이 됩니다. 건물은 높이가 내림차순으로 스택에 추가되므로 빠른 이진 검색이 가능합니다.

3. 쿼리 정렬:

   • 지수가 큰 건물을 먼저 처리하려면 쿼리를 b의 내림차순으로 정렬하세요. 이렇게 하면 높은 인덱스에서 낮은 인덱스로 이동할 때 스택을 효율적으로 구축할 수 있습니다.

4. 스택의 이진 검색:

   • 각 쿼리에 대해 단조 스택에서 이진 검색을 사용하여 조건을 만족하는 가장 작은 인덱스 t를 찾습니다.

계획

1. 두 지수(b) 중 더 큰 지수를 기준으로 내림차순으로 쿼리를 정렬합니다.
2. 유효한 인덱스의 단조로운 스택을 유지하면서 배열을 뒤로 탐색합니다.
3. 각 쿼리에 대해 사소한 사례(a == b 또는 heights[a] < heights[b])를 확인하세요.
4. 사소하지 않은 경우에는 스택을 사용하여 이진 검색을 통해 가장 왼쪽에 유효한 건물을 찾습니다.
5. 원래 쿼리 순서대로 결과를 반환합니다.

해결 단계

1. 쿼리 전처리:

   • 일관성을 위해 각 쿼리에서 a <= b를 확인하세요.
   • b를 기준으로 내림차순으로 검색어를 정렬합니다.

2. 쿼리 반복:

   • 배열을 탐색하면서 단조로운 스택을 유지합니다.
   • 각 검색어에 대해:
     • a == b이면 답은 b입니다.
     • 높이[a] < heights[b], 답은 b입니다.
     • 그렇지 않으면 스택을 사용하여 가장 작은 유효 인덱스 t > b.

   • 스택의 이진 검색:

     • 이진 검색을 사용하여 heights[t] >를 충족하는 스택에서 가장 작은 인덱스 t를 빠르게 찾습니다. 높이[a].

   • 원래 주문 복원:

     • 결과를 원래 쿼리 색인으로 다시 매핑합니다.

   • 결과 반환.

   이 솔루션을 PHP: 2940으로 구현해 보겠습니다. 앨리스와 밥이 만날 수 있는 건물 찾기
   

   <?php
   /**
    * @param Integer[] $heights
    * @param Integer[][] $queries
    * @return Integer[]
    */
   function leftmostBuildingQueries($heights, $queries) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
   }
   
   /**
    * @param $queries
    * @return array
    */
   private function getIndexedQueries($queries) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
   }
   
   /**
    * @param $stack
    * @param $a
    * @param $heights
    * @return mixed|null
    */
   private function findUpperBound($stack, $a, $heights) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
   }
   
   class IndexedQuery {
       public $queryIndex;
       public $a; // Alice's index
       public $b; // Bob's index
   
       /**
        * @param $queryIndex
        * @param $a
        * @param $b
        */
       public function __construct($queryIndex, $a, $b) {
           $this->queryIndex = $queryIndex;
           $this->a = $a;
           $this->b = $b;
       }
   }
   
   // Test the function
   $heights = [6, 4, 8, 5, 2, 7];
   $queries = [[0, 1], [0, 3], [2, 4], [3, 4], [2, 2]];
   print_r(leftmostBuildingQueries($heights, $queries));
   
   $heights = [5, 3, 8, 2, 6, 1, 4, 6];
   $queries = [[0, 7], [3, 5], [5, 2], [3, 0], [1, 6]];
   print_r(leftmostBuildingQueries($heights, $queries));
   ?>
   

   설명:

   1. 쿼리 정렬: 더 큰 인덱스를 먼저 처리하기 위해 쿼리는 b를 기준으로 내림차순으로 정렬됩니다. 이를 통해 처리하면서 단조로운 스택을 업데이트할 수 있습니다.
   2. 단조 스택: 스택은 앨리스와 밥이 만날 수 있는 인덱스 구축을 추적하는 데 사용됩니다. 이전에 본 건물보다 높이가 높은 건물만 스택에 보관합니다.
   3. 이진 검색: 각 쿼리에 응답할 때 이진 검색을 사용하여 조건이 충족되는 가장 작은 인덱스 t를 효율적으로 찾습니다.

   예시 연습

   입력:

   • 높이 = [6,4,8,5,2,7]
   • 쿼리 = [[0,1],[0,3],[2,4],[3,4],[2,2]]

   프로세스:

   1. 정렬 쿼리:

      • 색인된 쿼리: [(2,4), (3,4), (0,3), (0,1), (2,2)]

   2. 단조 스택 구축:

      • 가장 높은 인덱스에서 시작하여 스택에 인덱스를 추가합니다.
        • 인덱스 5: 스택 = [5]
        • 인덱스 4에서: 스택 = [5, 4]
        • ...

   3. 쿼리 처리:

      • 쿼리 [0,1]의 경우 heights[0] < heights[1]: 결과 = 2.
      • ...

   산출:

   [2, 5, -1, 5, 2]

   시간복잡도

   1. 쿼리 정렬: O(Q log Q) 여기서 Q는 쿼리 수입니다.
   2. 단조 스택 구성: O(N) 여기서 N은 높이의 길이입니다.
   3. 각 쿼리에 대한 이진 검색: O(Q log N).

   전체: O(N Q log(Q N)).

   예시 출력

   입력:
   

   $heights = [6, 4, 8, 5, 2, 7];
   $queries = [[0, 1], [0, 3], [2, 4], [3, 4], [2, 2]];
   

   출력:
   

   print_r(findBuilding($heights, $queries)); // [2, 5, -1, 5, 2]
   

   이 접근 방식은 단조 스택과 이진 검색을 활용하여 대규모 제약 조건을 효율적으로 처리합니다. 정확성을 유지하면서 최적의 쿼리 처리를 보장합니다.

   연락처 링크

   이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

   이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

   • 링크드인
   • 깃허브

   위 내용은 앨리스와 밥이 만날 수 있는 건물 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!