문제
You are given a 0-indexed array heights of positive integers, where heights[i] represents the height of the ith building.
If a person is in building i, they can move to any other building j if and only if i < j and heights[i] < heights[j].
You are also given another array queries where queries[i] = [ai, bi]. On the ith query, Alice is in building ai while Bob is in building bi.
Return an array ans where ans[i] is the index of the leftmost building where Alice and Bob can meet on the ith query. If Alice and Bob cannot move to a common building on query i, set ans[i] to -1.양의 정수로 이루어진 0-indexed 배열 heights가 주어집니다. heights[i]는 i번째 건물의 높이를 나타냅니다.
어떤 사람이 i번 건물에 있을 때, 다음 조건을 모두 만족하는 경우에만 다른 건물 j로 이동할 수 있습니다.
i < jheights[i] < heights[j]
또한 queries[i] = [ai, bi] 형태의 배열 queries가 주어집니다. i번째 쿼리에서 Alice는 ai번 건물에 있고, Bob은 bi번 건물에 있습니다.
각 쿼리에 대해 Alice와 Bob이 만날 수 있는 가장 왼쪽 건물의 인덱스를 ans[i]로 하는 배열 ans를 반환하세요.
만약 i번째 쿼리에서 Alice와 Bob이 공통으로 이동할 수 있는 건물이 없다면 ans[i]를 -1로 설정하세요.
예시
입력: heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
출력: [2,5,-1,5,2]
설명:
첫 번째 쿼리에서 heights[0] < heights[2]이고 heights[1] < heights[2]이므로 Alice와 Bob은 2번 건물로 이동할 수 있습니다.
두 번째 쿼리에서 heights[0] < heights[5]이고 heights[3] < heights[5]이므로 Alice와 Bob은 5번 건물로 이동할 수 있습니다.
세 번째 쿼리에서는 Alice가 다른 어떤 건물로도 이동할 수 없으므로 Bob과 만날 수 없습니다.
네 번째 쿼리에서 heights[3] < heights[5]이고 heights[4] < heights[5]이므로 Alice와 Bob은 5번 건물로 이동할 수 있습니다.
다섯 번째 쿼리에서 Alice와 Bob은 이미 같은 건물에 있습니다.
ans[i] != -1인 경우, ans[i]가 Alice와 Bob이 만날 수 있는 가장 왼쪽 건물임을 알 수 있습니다.
ans[i] == -1인 경우, Alice와 Bob이 만날 수 있는 건물이 존재하지 않음을 알 수 있습니다.
제한
풀이
1. 세그먼트 트리를 사용하기
단일 쿼리가 [a, b] 일때 먼저 a가 작은 값이 되도록 바꿔준다.
- 만약 a와 b가 같다면
- 이동할 필요 없이 a로 설정한다.
- 만약 b의 높이가 더 높다면
- a가 바로 b로 이동할수 있기 때문에 b로 설정한다.
두가지 모두 아닐경우
- height[a]보단 크지만 인덱스는 b의 오른쪽에 있는 가장 인덱스가 작은것으로 설정한다.
- 이것을 우리는 최댓값을 저장한 세그먼트 트리를 이용해 구할수 있다.
class NumArray:
def __init__(self, nums: List[int]):
self.n = len(nums)
self.tree = [0] * (4 * self.n)
self._build(nums, 1, 0, self.n - 1)
def _build(
self,
nums: List[int],
node: int,
left: int,
right: int,
) -> None:
if left == right:
self.tree[node] = nums[left]
return
mid = (left + right) // 2
self._build(nums, node * 2, left, mid)
self._build(nums, node * 2 + 1, mid + 1, right)
self.tree[node] = max(self.tree[node * 2], self.tree[node * 2 + 1])
def _query(
self,
node: int,
seg_left: int,
seg_right: int,
qur_left: int,
qur_right: int,
target: int,
) -> int:
if seg_right < qur_left or qur_right < seg_left or self.tree[node] <= target:
return -1
mid = (seg_left + seg_right) // 2
if qur_left <= seg_left <= seg_right <= qur_right:
if seg_left == seg_right:
return seg_left
if self.tree[node * 2] > target:
return self._query(node * 2, seg_left, mid, qur_left, qur_right, target)
else:
return self._query(
node * 2 + 1, mid + 1, seg_right, qur_left, qur_right, target
)
left = self._query(node * 2, seg_left, mid, qur_left, qur_right, target)
if left != -1:
return left
return self._query(
node * 2 + 1, mid + 1, seg_right, qur_left, qur_right, target
)
def query(self, left: int, right: int, target: int) -> int:
return self._query(1, 0, self.n - 1, left, right, target)
class Solution:
def leftmostBuildingQueries(
self, heights: List[int], queries: List[List[int]]
) -> List[int]:
H = len(heights)
Q = len(queries)
ans = [-1] * Q
na = NumArray(heights)
for i, (a, b) in enumerate(queries):
if a > b:
a, b = b, a
if a == b:
ans[i] = a
elif heights[a] < heights[b]:
ans[i] = b
else:
ans[i] = na.query(b + 1, H - 1, heights[a])
return ans