leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2940.cpp (1519B)

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 };