题解-找到 Alice 和 Bob 可以相遇的建筑-单调栈+二分+离线

Problem: 100110. 找到 Alice 和 Bob 可以相遇的建筑

思路

• 分解一下题目,发现和Alice和Bob二人顺序没关系,为了方便,我们假设Alice所在建筑位置在左边,称为a,bob就会在右边,称为b
• 假设a,b相等,则所在的位置就是b
• 若b所在高度大于a,则答案是b
• 剩下的就是我们要考虑的一般情况:b的高度小于a,

解题方法

• 我们要做的明确,查b的右侧大于a的第一个建筑
• 每次都向后查询显然时间复杂度不够,遍历q又是必须的,所以我们想把这个查询压到log级别
• 显然可以通过维护右侧单调栈+二分的模式
• 但是为每一个点都配单调栈内存不够
• 我们发现左边的单调栈一定是右边的转过来的
• 所以我们只需要维护一个单调栈
• 在遇到对于要处理的点的查询的时候直接查询就行
• 也就是我们总体过程是离线查询+单调栈+二分

代码细节

1. 我们先用哈希表记录查询,保证不漏:
2. 先保证a<=b
3. 以b为key,存储想查询的值:a和答案位置i
4. 需要注意的是可能存在多个a的情况,需要用列表而不是一一对应
5. 从后向前遍历,维护单调栈
6. 对于遍历的点,如果在哈希表内,说明其是b
7. 现在维护的单调栈满足需求
8. 二分查到的答案再写回相应的位置

Code

class Solution:    
    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
        n=len(queries)  
        hash={}#记录b对应的a和index
        for i in range(n):
            a=min(queries[i])
            b=max(queries[i])
            if b not in hash:
                hash[b]=[]
            hash[b].append([a,i])
    #记录右边单调递增
    st=[]
    res=[-1]*n
    for i in range(len(heights)-1,-1,-1):
        h=heights[i]
        while st and h>heights[st[-1]]:
            st.pop()
        st.append(i)
        if i in hash:
            b=i
            for a,index in hash[i]:
                if heights[b]>heights[a] or a==b:
                    res[index]=b
                else:
                    l,r=0,len(st)-1
                    while l<=r:
                        mid=(l+r)//2
                        if heights[st[mid]]>heights[a]:
                            l=mid+1
                        else:
                            r=mid-1
                    if (l-1<0):
                        res[index]=-1
                    else:
                        res[index]=st[l-1]
    return res</code></pre>