leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

2940.cpp (1519B)

      1 class Solution {
      2     static int search(int height, const vector<pair<int, int>> &st) {
      3         int low = 0, high = size(st) - 1;
      4         int ans = -1;
      5 
      6         while (low <= high) {
      7             const int mid = low + (high - low) / 2;
      8 
      9             if (st[mid].first > height) {
     10                 ans = max(ans, mid);
     11                 low = mid + 1;
     12             } else {
     13                 high = mid - 1;
     14             }
     15         }
     16 
     17         return ans;
     18     }
     19 
     20   public:
     21     vector<int> leftmostBuildingQueries(const vector<int> &heights, const vector<vector<int>> &queries) {
     22         const int n = size(heights), m = size(queries);
     23         vector<vector<pair<int, int>>> nqueries(n);
     24         vector<int> res(m, -1);
     25 
     26         for (int i = 0; i < m; i++) {
     27             int a = queries[i][0];
     28             int b = queries[i][1];
     29 
     30             if (a > b) swap(a, b);
     31             if (heights[b] > heights[a] || a == b)
     32                 res[i] = b;
     33             else
     34                 nqueries[b].emplace_back(heights[a], i);
     35         }
     36 
     37         vector<pair<int, int>> st;
     38         for (int i = n - 1; i >= 0; i--) {
     39             for (const auto &[a, b] : nqueries[i]) {
     40                 const auto pos = search(a, st);
     41                 if (pos >= 0 && pos < size(st)) {
     42                     res[b] = st[pos].second;
     43                 }
     44             }
     45 
     46             while (!st.empty() && st.back().first <= heights[i]) {
     47                 st.pop_back();
     48             }
     49 
     50             st.emplace_back(heights[i], i);
     51         }
     52 
     53         return res;
     54     }
     55 };