leetcode

0 class Solution {

1 static int search(int height, const vector<pair<int, int>> &st) {

2 int low = 0, high = size(st) - 1;

3 int ans = -1;

4

5 while (low <= high) {

6 const int mid = low + (high - low) / 2;

7

8 if (st[mid].first > height) {

9 ans = max(ans, mid);

10 low = mid + 1;

11 } else {

12 high = mid - 1;

13 }

14 }

15

16 return ans;

17 }

18

19 public:

20 vector<int> leftmostBuildingQueries(const vector<int> &heights, const vector<vector<int>> &queries) {

21 const int n = size(heights), m = size(queries);

22 vector<vector<pair<int, int>>> nqueries(n);

23 vector<int> res(m, -1);

24

25 for (int i = 0; i < m; i++) {

26 int a = queries[i][0];

27 int b = queries[i][1];

28

29 if (a > b) swap(a, b);

30 if (heights[b] > heights[a] || a == b)

31 res[i] = b;

32 else

33 nqueries[b].emplace_back(heights[a], i);

34 }

35

36 vector<pair<int, int>> st;

37 for (int i = n - 1; i >= 0; i--) {

38 for (const auto &[a, b] : nqueries[i]) {

39 const auto pos = search(a, st);

40 if (pos >= 0 && pos < size(st)) {

41 res[b] = st[pos].second;

42 }

43 }

44

45 while (!st.empty() && st.back().first <= heights[i]) {

46 st.pop_back();

47 }

48

49 st.emplace_back(heights[i], i);

50 }

51

52 return res;

53 }

54 };