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

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

• 数组遍历与处理
• 滑动窗口思想
• 双端队列的应用

题目解答方法的文字分析

题目要求在给定整数数组 heights 和整数 k 的情况下，找到一个合适的地区范围，使得该范围内的高度差不超过 k，并且范围最大。为了解决这个问题，我们采用滑动窗口的思想，并使用双端队列来维护当前窗口内的高度索引。

我们使用两个双端队列 maxDq 和 minDq 分别来维护当前窗口内的高度索引，其中 maxDq 用于找到当前窗口内的最大高度，而 minDq 用于找到当前窗口内的最小高度。

我们同时维护两个指针 left 和 right，表示滑动窗口的左右边界。开始时，两个指针都指向数组的起始位置。

我们不断右移右指针 right，在右移的过程中，维护双端队列 maxDq 和 minDq，使其保持高度索引对应的值递增和递减顺序，并确保队列内的高度差不超过 k。

如果当前窗口内的最大和最小高度的差大于 k，说明当前窗口不满足条件，需要调整左指针 left，使窗口范围变小，直到满足条件。

记录当前合适范围的长度，不断更新最大范围 maxRange。

继续右移右指针 right，重复上述过程，直到右指针遍历完整个数组。

class Solution {
public:
    int findMaxRangeWithinThreshold(vector<int>& heights, int k) {
        deque<int> maxDq; // 有序双端队列，存储当前窗口内的高度索引，队头是最大值的索引
        deque<int> minDq; // 有序双端队列，存储当前窗口内的高度索引，队头是最小值的索引
        int left = 0; // 滑动窗口的左边界
        int maxRange = 0; // 记录最大的合适范围长度

        for (int right = 0; right < heights.size(); ++right) {
            // 维护有序双端队列 maxDq 和 minDq，使其保持高度对应的值递增和递减顺序
            while (!maxDq.empty() && heights[right] >= heights[maxDq.back()]) {
                maxDq.pop_back();
            }
            maxDq.push_back(right);

            while (!minDq.empty() && heights[right] <= heights[minDq.back()]) {
                minDq.pop_back();
            }
            minDq.push_back(right);

            // 如果当前窗口内的最大和最小高度的差大于k，更新左边界left
            while (heights[maxDq.front()] - heights[minDq.front()] > k) {
                ++left;
                if (maxDq.front() < left) {
                    maxDq.pop_front();
                }
                if (minDq.front() < left) {
                    minDq.pop_front();
                }
            }

            // 计算当前合适范围的长度，更新最大范围maxRange
            maxRange = max(maxRange, right - left + 1);
        }

        return maxRange;
    }
};