Question

2940. 找到 Alice 和 Bob 可以相遇的建筑

English Version

题目描述

给你一个下标从 0 开始的正整数数组 heights ，其中 heights[i] 表示第 i 栋建筑的高度。

如果一个人在建筑 i ，且存在 i < j 的建筑 j 满足 heights[i] < heights[j] ，那么这个人可以移动到建筑 j 。

给你另外一个数组 queries ，其中 queries[i] = [ai, bi] 。第 i 个查询中，Alice 在建筑 ai ，Bob 在建筑 bi 。

请你能返回一个数组 ans ，其中 ans[i] 是第 i 个查询中，Alice 和 Bob 可以相遇的 最左边的建筑 。如果对于查询 i ，Alice_ _和_ _Bob 不能相遇，令 ans[i] 为 -1 。

 

示例 1：

输入：heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
输出：[2,5,-1,5,2]
解释：第一个查询中，Alice 和 Bob 可以移动到建筑 2 ，因为 heights[0] < heights[2] 且 heights[1] < heights[2] 。
第二个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[0] < heights[5] 且 heights[3] < heights[5] 。
第三个查询中，Alice 无法与 Bob 相遇，因为 Alice 不能移动到任何其他建筑。
第四个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[3] < heights[5] 且 heights[4] < heights[5] 。
第五个查询中，Alice 和 Bob 已经在同一栋建筑中。
对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。

示例 2：

输入：heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]
输出：[7,6,-1,4,6]
解释：第一个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[0] < heights[7] 。
第二个查询中，Alice 和 Bob 可以移动到建筑 6 ，因为 heights[3] < heights[6] 且 heights[5] < heights[6] 。
第三个查询中，Alice 无法与 Bob 相遇，因为 Bob 不能移动到任何其他建筑。
第四个查询中，Alice 和 Bob 可以移动到建筑 4 ，因为 heights[3] < heights[4] 且 heights[0] < heights[4] 。
第五个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[1] < heights[6] 。
对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。

 

提示：

• 1 <= heights.length <= 5 * 104
• 1 <= heights[i] <= 109
• 1 <= queries.length <= 5 * 104
• queries[i] = [ai, bi]
• 0 <= ai, bi <= heights.length - 1

解法

方法一：树状数组

我们不妨记 $queries[i] = [l_i, r_i]$，其中 $l_i \le r_i$。如果 $l_i = r_i$ 或者 $heights[l_i] \lt heights[r_i]$，那么答案就是 $r_i$。否则，我们需要在所有满足 $j \gt r_i$，且 $heights[j] \gt heights[l_i]$ 的 $j$ 中找到最小的 $j$。

我们可以将 $queries$ 按照 $r_i$ 从大到小排序，用一个指针 $j$ 指向当前遍历到的 $heights$ 的下标。

接下来，我们遍历每个查询 $queries[i] = (l, r)$，对于当前查询，如果 $j \gt r$，那么我们循环将 $heights[j]$ 插入树状数组中。树状数组维护的是后缀高度（离散化后的高度）的下标的最小值。然后，我们判断是否满足 $l = r$ 或者 $heights[l] \lt heights[r]$，如果满足，那么当前查询的答案就是 $r$，否则，我们在树状数组中查询 $heights[l]$ 的下标的最小值，即为当前查询的答案。

时间复杂度 $O((n + m) \times \log n + m \times \log m)$，空间复杂度 $O(n + m)$。其中 $n$ 和 $m$ 分别为 $heights$ 和 $queries$ 的长度。

相似题目：

• 2736. 最大和查询

class BinaryIndexedTree:
  __slots__ = ["n", "c"]

  def __init__(self, n: int):
    self.n = n
    self.c = [inf] * (n + 1)

  def update(self, x: int, v: int):
    while x <= self.n:
      self.c[x] = min(self.c[x], v)
      x += x & -x

  def query(self, x: int) -> int:
    mi = inf
    while x:
      mi = min(mi, self.c[x])
      x -= x & -x
    return -1 if mi == inf else mi


class Solution:
  def leftmostBuildingQueries(
    self, heights: List[int], queries: List[List[int]]
  ) -> List[int]:
    n, m = len(heights), len(queries)
    for i in range(m):
      queries[i] = [min(queries[i]), max(queries[i])]
    j = n - 1
    s = sorted(set(heights))
    ans = [-1] * m
    tree = BinaryIndexedTree(n)
    for i in sorted(range(m), key=lambda i: -queries[i][1]):
      l, r = queries[i]
      while j > r:
        k = n - bisect_left(s, heights[j]) + 1
        tree.update(k, j)
        j -= 1
      if l == r or heights[l] < heights[r]:
        ans[i] = r
      else:
        k = n - bisect_left(s, heights[l])
        ans[i] = tree.query(k)
    return ans

class BinaryIndexedTree {
  private final int inf = 1 << 30;
  private int n;
  private int[] c;

  public BinaryIndexedTree(int n) {
    this.n = n;
    c = new int[n + 1];
    Arrays.fill(c, inf);
  }

  public void update(int x, int v) {
    while (x <= n) {
      c[x] = Math.min(c[x], v);
      x += x & -x;
    }
  }

  public int query(int x) {
    int mi = inf;
    while (x > 0) {
      mi = Math.min(mi, c[x]);
      x -= x & -x;
    }
    return mi == inf ? -1 : mi;
  }
}

class Solution {
  public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {
    int n = heights.length;
    int m = queries.length;
    for (int i = 0; i < m; ++i) {
      if (queries[i][0] > queries[i][1]) {
        queries[i] = new int[] {queries[i][1], queries[i][0]};
      }
    }
    Integer[] idx = new Integer[m];
    for (int i = 0; i < m; ++i) {
      idx[i] = i;
    }
    Arrays.sort(idx, (i, j) -> queries[j][1] - queries[i][1]);
    int[] s = heights.clone();
    Arrays.sort(s);
    int[] ans = new int[m];
    int j = n - 1;
    BinaryIndexedTree tree = new BinaryIndexedTree(n);
    for (int i : idx) {
      int l = queries[i][0], r = queries[i][1];
      while (j > r) {
        int k = n - Arrays.binarySearch(s, heights[j]) + 1;
        tree.update(k, j);
        --j;
      }
      if (l == r || heights[l] < heights[r]) {
        ans[i] = r;
      } else {
        int k = n - Arrays.binarySearch(s, heights[l]);
        ans[i] = tree.query(k);
      }
    }
    return ans;
  }
}

class BinaryIndexedTree {
private:
  int inf = 1 << 30;
  int n;
  vector<int> c;

public:
  BinaryIndexedTree(int n) {
    this->n = n;
    c.resize(n + 1, inf);
  }

  void update(int x, int v) {
    while (x <= n) {
      c[x] = min(c[x], v);
      x += x & -x;
    }
  }

  int query(int x) {
    int mi = inf;
    while (x > 0) {
      mi = min(mi, c[x]);
      x -= x & -x;
    }
    return mi == inf ? -1 : mi;
  }
};

class Solution {
public:
  vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
    int n = heights.size(), m = queries.size();
    for (auto& q : queries) {
      if (q[0] > q[1]) {
        swap(q[0], q[1]);
      }
    }
    vector<int> idx(m);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int i, int j) {
      return queries[j][1] < queries[i][1];
    });
    vector<int> s = heights;
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    vector<int> ans(m);
    int j = n - 1;
    BinaryIndexedTree tree(n);
    for (int i : idx) {
      int l = queries[i][0], r = queries[i][1];
      while (j > r) {
        int k = s.end() - lower_bound(s.begin(), s.end(), heights[j]) + 1;
        tree.update(k, j);
        --j;
      }
      if (l == r || heights[l] < heights[r]) {
        ans[i] = r;
      } else {
        int k = s.end() - lower_bound(s.begin(), s.end(), heights[l]);
        ans[i] = tree.query(k);
      }
    }
    return ans;
  }
};

const inf int = 1 << 30

type BinaryIndexedTree struct {
  n int
  c []int
}

func NewBinaryIndexedTree(n int) BinaryIndexedTree {
  c := make([]int, n+1)
  for i := range c {
    c[i] = inf
  }
  return BinaryIndexedTree{n: n, c: c}
}

func (bit *BinaryIndexedTree) update(x, v int) {
  for x <= bit.n {
    bit.c[x] = min(bit.c[x], v)
    x += x & -x
  }
}

func (bit *BinaryIndexedTree) query(x int) int {
  mi := inf
  for x > 0 {
    mi = min(mi, bit.c[x])
    x -= x & -x
  }
  if mi == inf {
    return -1
  }
  return mi
}

func leftmostBuildingQueries(heights []int, queries [][]int) []int {
  n, m := len(heights), len(queries)
  for _, q := range queries {
    if q[0] > q[1] {
      q[0], q[1] = q[1], q[0]
    }
  }
  idx := make([]int, m)
  for i := range idx {
    idx[i] = i
  }
  sort.Slice(idx, func(i, j int) bool { return queries[idx[j]][1] < queries[idx[i]][1] })
  s := make([]int, n)
  copy(s, heights)
  sort.Ints(s)
  ans := make([]int, m)
  tree := NewBinaryIndexedTree(n)
  j := n - 1
  for _, i := range idx {
    l, r := queries[i][0], queries[i][1]
    for ; j > r; j-- {
      k := n - sort.SearchInts(s, heights[j]) + 1
      tree.update(k, j)
    }
    if l == r || heights[l] < heights[r] {
      ans[i] = r
    } else {
      k := n - sort.SearchInts(s, heights[l])
      ans[i] = tree.query(k)
    }
  }
  return ans
}

class BinaryIndexedTree {
  private n: number;
  private c: number[];
  private inf: number = 1 << 30;

  constructor(n: number) {
    this.n = n;
    this.c = Array(n + 1).fill(this.inf);
  }

  update(x: number, v: number): void {
    while (x <= this.n) {
      this.c[x] = Math.min(this.c[x], v);
      x += x & -x;
    }
  }

  query(x: number): number {
    let mi = this.inf;
    while (x > 0) {
      mi = Math.min(mi, this.c[x]);
      x -= x & -x;
    }
    return mi === this.inf ? -1 : mi;
  }
}

function leftmostBuildingQueries(heights: number[], queries: number[][]): number[] {
  const n = heights.length;
  const m = queries.length;
  for (const q of queries) {
    if (q[0] > q[1]) {
      [q[0], q[1]] = [q[1], q[0]];
    }
  }
  const idx: number[] = Array(m)
    .fill(0)
    .map((_, i) => i);
  idx.sort((i, j) => queries[j][1] - queries[i][1]);
  const tree = new BinaryIndexedTree(n);
  const ans: number[] = Array(m).fill(-1);
  const s = [...heights];
  s.sort((a, b) => a - b);
  const search = (x: number) => {
    let [l, r] = [0, n];
    while (l < r) {
      const mid = (l + r) >> 1;
      if (s[mid] >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  };
  let j = n - 1;
  for (const i of idx) {
    const [l, r] = queries[i];
    while (j > r) {
      const k = n - search(heights[j]) + 1;
      tree.update(k, j);
      --j;
    }
    if (l === r || heights[l] < heights[r]) {
      ans[i] = r;
    } else {
      const k = n - search(heights[l]);
      ans[i] = tree.query(k);
    }
  }
  return ans;
}