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

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

• 思路
• 解题方法
• 代码细节
• Code

思路

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

解题方法

• 我们要做的明确,查b的右侧大于a的第一个建筑

• 每次都向后查询显然时间复杂度不够,遍历q又是必须的,所以我们想把这个查询压到log级别

• 显然可以通过维护右侧单调栈+二分的模式

  • 但是为每一个点都配单调栈内存不够

• 我们发现左边的单调栈一定是右边的转过来的

• 所以我们只需要维护一个单调栈,在遇到对于要处理的点的查询的时候直接查询就行

• 也就是我们总体过程是离线查询+单调栈+二分

代码细节

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

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