题解 | #寻找最合适的生育区域# 双指针

知识点

双指针

思路

维护双指针，右指针每次向右移动一次，表示当前的末尾位置，左指针移动到满足最大元素和最小元素的差值小于等于k的最左位置，更新答案。

维护最大最小值可以用multiset或者map实现。

时间复杂度是

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int findMaxRangeWithinThreshold(vector<int>& heights, int k) {
        int res = 0;
        multiset<int> S;
        for (int i = 0, j = 0; i < heights.size(); i ++) {
            S.insert(heights[i]);
            while (S.size() and *S.rbegin() - *S.begin() > k) {
                S.erase(S.find(heights[j ++]));
            }
            res = max(res, i - j + 1);
        }
        return res;
    }
};