样例

blablabla

class Solution {
public:
    int findLatestStep(vector<int>& arr, int m) {

        int n = arr.size();
        if (n == m) {
            return n;
        }
        map<int, int> s = { {1,n} };
        for (int i = n - 1; i >= 0; --i) {
            // lower_bound返回指向范围[first, last) 中首个不小于（即大于或等于） value 的元素的迭代器，或若找不到这种元素则返回 last 。
            // upper_bound  返回的是第一个大于 val 的 迭代器

            //map::lower_bound(key) :返回map中第一个大于或等于key的迭代器指针
            //map::upper_bound(key) :返回map中第一个大于key的迭代器指针

            //使用方法与next相似，不同的是prev返回的是it的第n个前驱迭代指针 默认长度为1 

            auto it = prev(s.upper_bound(arr[i]));
            /*
            std::vector<int> v{ 3, 1, 4 };
            auto it = v.end();
            auto pv = std::prev(it, 2);
            std::cout << *pv << '\n';    输出 1
            */
            auto [l, r] = *it;
            if (arr[i] - l == m || r - arr[i] == m){
                return i;
            }
            s.erase(it);
            if (l <= arr[i] - 1) s.emplace(l, arr[i] - 1);
            if (r >= arr[i] + 1)s.emplace(arr[i] + 1, r);
        }

        return -1;


    }
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla