[LeetCode] 2940. Find Building Where Alice and Bob Can Meet

https://leetcode.com/problems/find-building-where-alice-and-bob-can-meet/description/

leetcode - Find Building Where Alice and Bob Can Meet

문제 유형: 이진 탐색, 모노토닉 스택

문제 난이도: Hard

 

문제

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.

 

양의정수배열 heights가 주어집니다. heights[i] = i번째건물의 높이 입니다.

만약 사람이 i번째 건물에 있으면, i < j이고 height[i] < height[j]인 건물 j번건무로 이동할 수 있습니다.

 

Alice와 Bob의 위치가 queries[i] = [a_i, b_i]로 주어집니다.

두 사람이 만날 수 있는 가장 왼쪽의 건물을 구하시오.

없으면 -1을 반환하시오.

 

풀이

우선, a와 b중에서 더 뒤의 인덱스를 b로 한다.

그런 경우에서 b가 a보다 더 높거나 a = b인 경우, 해당 쿼리에 대한 응답은 b이다.

그게 아니라면, 공통된 이동가능한 건물을 찾아야 한다.

우선, b에서 만날 수 있는 쿼리의 응답에 대해서는 b로 채워넣고, 그게 아니면, newQueries[b]에 넣는다.

newQueries[j]에는 j번째 건물을 b로 하는 추가 조사가 필요한 쿼리정보가 들어있다. 안에는 {heights[a], i}를 추가한다.

heights[a]로 타켓 높이를 구하는 데 쓰이고, i는 쿼리 인덱스에 쓰인다.

 

모노토닉 스택에는 높이기준 내림차순으로 값을 유지시킨다.

heights배열을 뒤부터 다음과 같이 순회한다: 

  우선, 미리 현재의 모노토닉 스택의 크기를 계산하고, newQueries[i]에 있는 각 쿼리들에 대해 모노토닉 스택에서 이진탐색하여 유효한 결과가 나오면, 쿼리응답배열에 새로 업데이트한다.

  모노토닉 스택의 뒷부분에 있는 작거나 같은 값들은 모두 pop한다.

  그 뒤, {heights[i], i}를 넣는다.

 

이진탐색부분은 다음과 같다:

  만약 mid가 heigth보다 크면, 유효하므로 리턴값을 업데이트하고, left를 mid+1로 옮겨서 범위를 큰 쪽으로 좁혀본다.

  아니라면, right를 mid-1로 옮겨서 범위를 작은쪽으로 좁혀본다.

 

코드

C++

class Solution {
public:
    int search(int height, vector<pair<int, int>>& monos) {
        int l = 0;
        int r = monos.size()-1;
        int ans = -1;
        while(l <= r) {
            int mid = (l+r)/2;
            if(monos[mid].first > height) {
                ans = max(ans, mid);
                l = mid+1;
            } else r = mid-1;
        }
        return ans;
    }
    vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
        int n = heights.size(), m = queries.size();
        vector<pair<int, int>> monos;
        vector<int> ans(m, -1);
        vector<vector<pair<int, int>>> newQueries(n);
        for(int i = 0; i < m; ++i) {
            int a = queries[i][0];
            int b = queries[i][1];
            if(a > b) swap(a, b);
            if(heights[b] > heights[a] || a == b) {
                ans[i] = b;
            } else {
                newQueries[b].push_back({heights[a], i});
            }
        }

        for(int i = n-1; i >= 0; --i) {
            int size = monos.size();
            for(const auto &[a, b] : newQueries[i]) {
                int pos = search(a, monos);
                if(pos < size && pos >= 0) ans[b] = monos[pos].second;
            }
            while(!monos.empty() && monos.back().first <= heights[i]) 
                monos.pop_back();
            monos.push_back({heights[i], i});
        }
        return ans;
    }
};