1438. 绝对差不超过限制的最长连续子数组

一、题目

二、思路

2.1 解题思路

滑动窗口

2.2 代码尝试

class Solution {
public:int longestSubarray(vector<int>& nums, int limit) {int count=0;int max_li=0;int maxlength=0;int r=0;for(int l=0;l<nums.size();l++){//当左边界固定时，不断往右扩展max_li=0;//置零if(r==nums.size()-1){return maxlength;}//窗口先一直滑动到满足条件的边界while(r<nums.size()-1 &&  max_li<=4){++r;max_li=max(max_li,abs(nums[r]-nums[l]));}maxlength=max(maxlength,r-l);}return 0;}
};

感觉对滑动窗口本质还是有点不理解，往哪里滑动然后while就应该怎么写

2.3 疑难问题

2.4 代码复盘

你在代码中使用 max_li 来记录当前窗口内的最大差值，但你在每次左边界移动时都将 max_li 重置为 0。这会导致你在计算窗口内的差值时丢失之前的信息。确实，这个置零有点笨重了。
你的算法时间复杂度较高。每次左边界移动时，右边界都从当前位置重新开始扩展，这会导致时间复杂度为 O(n^2)。你可以使用滑动窗口结合单调队列来优化时间复杂度到 O(n)。

三、解法

class Solution {
public:int longestSubarray(vector<int>& nums, int limit) {multiset<int> s;int n = nums.size();int left = 0, right = 0;int ret = 0;while (right < n) {s.insert(nums[right]);while (*s.rbegin() - *s.begin() > limit) {s.erase(s.find(nums[left++]));}ret = max(ret, right - left + 1);right++;}return ret;}
};作者：力扣官方题解
链接：https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/solutions/612688/jue-dui-chai-bu-chao-guo-xian-zhi-de-zui-5bki/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

四、收获

4.1 心得

红黑树能存最大最小值。能够快速找到最大值和最小值。感觉被上一道变体题目给搞乱了，这题也是个模板，但就是做不出来了。

4.2 举一反三

不定长滑动窗口的模板

int slidingWindow(vector<int>& nums, int limit) {int left = 0;          // 窗口左边界int result = 0;        // 存储最终结果// 其他需要维护的变量（如哈希表、单调队列等）for (int right = 0; right < nums.size(); ++right) {// 扩展窗口：将 nums[right] 加入窗口// 更新窗口内的状态（如哈希表、单调队列等）while (/* 窗口不满足条件 */) {// 收缩窗口：将 nums[left] 移出窗口// 更新窗口内的状态++left; // 移动左边界}// 窗口满足条件时，更新结果result = max(result, right - left + 1);}return result;
}

在滑动窗口算法中，while (/* 窗口不满足条件 */) 的作用是 收缩窗口，以确保窗口内的元素始终满足题目要求的条件。这是滑动窗口算法的核心逻辑之一。
使用 while 可以确保窗口内的元素始终满足条件，从而保证结果的正确性。