【Leetcode Daily】1438绝对差不超过限制的最长连续子数组

发表于2025-09-06|更新于2025-09-06|力扣日常 | LeetcodeDaily

|总字数:305|阅读时长:1分钟|浏览量:

题目浅析

想查看原题可以点击题目链接。
简单地说，就是给一个数组和一个限制数字 limit，要求返回一个最长连续子数的长度，其中任意两个数字之差不能超过 limit

思路分享

通过滑动窗口的思路，可以遍历其中所有限制值之内的窗口，问题是如何快速判断当前窗口是否合法。
单调队列的功能在于，方便地维护一定区间内的最值。而单调栈看似类似，实则更适合找对某个值的下个更小或者更大的情况，是比较级，不是最级。

https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/solutions/3707019/on-zuo-fa-hua-dong-chuang-kou-dan-diao-d-g45r/

代码解答（强烈建议自行解答后再看）

参考题解

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        max_q = deque()
        min_q = deque()
        res = 0
        left = 0
        for i, x in enumerate(nums):
            while max_q and x > nums[max_q[-1]]:
                max_q.pop()
            max_q.append(i)
            while min_q and x < nums[min_q[-1]]:
                min_q.pop()
            min_q.append(i)

            while nums[max_q[0]] - nums[min_q[0]] > limit:
                left += 1
                if left > max_q[0]:
                    max_q.popleft()
                if left > min_q[0]:
                    min_q.popleft()          

            res = max(res, i-left+1)
            
        return res

文章作者: 陆爻齐-LuYaoQi

文章链接: http://hslix.github.io/posts/d5c461ca.html

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！

Algorithm 队列

相关推荐

【Leetcode Daily】933最近的请求次数

题目浅析想查看原题可以点击题目链接。简单地说，就是自己实现一个类，能够存储数字（给的数字按升序排列），同时每次插入数字都会返回已有数字中数值上最近 3000 的个数。思路分享参考题解中，用队列先进先出的特性，保持队首和队尾差值不超过 3000，否则开始弹队尾。也可以不用队列，在存储数字后，可以二分查找队首元素减 3000 的位置，然后就可以计算出有多少数字了。 https://leetcode.cn/problems/number-of-recent-calls/solutions/1472153/-by-fuxuemingzhu-ryxx/ 代码解答（强烈建议自行解答后再看）参考题解 123456789101112131415class RecentCounter: def __init__(self): self.que = deque() def ping(self, t: int) -> int: self.que.append(t) while self.que[-1] -...

【Leetcode Daily】950按递增顺序显示卡牌

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个取数组数的方法，就是弹出最左边的数，并把下一个数放末尾，直到所有数都被弹出。现在给出初始数组的顺序，使得按方法取出的数是递增顺序的。思路分享本题有两个难点，第一个是读题，从本题我发现我已经有相当的时间没有好好读东西了，读到题目也心烦意乱，导致获取上面的题意都有些困难；第二个是逆思维，这题乍一看没思路，但是实际上要得到那个“初始顺序”，所需的最终的顺序和得到顺序的过程都有了，只要对着升序的数字执行倒过来的行动（把末位数提前，然后在左边加一个数）代码解答（强烈建议自行解答后再看）参考题解 12345678910class Solution: def deckRevealedIncreasing(self, deck: List[int]) -> List[int]: deck.sort() q = deque() while deck: if q: q.appendleft(q.pop()) ...

【Leetcode Daily】1670设计前中后队列

题目浅析想查看原题可以点击题目链接。简单地说，就是设计一个队列，支持在这个队列的前中后三个地方进行入队和出队的操作。思路分享借鉴灵山的不错的思路，用两个队列来模拟，规定，两个队列大小相同时，优先入队右侧，所以出队时也优先右侧的左端。 https://leetcode.cn/problems/design-front-middle-back-queue/solutions/2544784/tu-jie-liang-ge-shuang-duan-dui-lie-jian-43pr/ 代码解答（强烈建议自行解答后再看）参考题解 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354class FrontMiddleBackQueue: def __init__(self): self.left = deque() self.right = deque() def...

【Leetcode Daily】239滑动窗口最大值

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个数组和一个数字 k，请给出这个数组中，所有连续 k 个数字中最大的那个数。思路分享题目其实已经说明了本题的核心就是滑动窗口了，滑动窗口核心的三步就是进入窗口，弹出窗口，记录数据。但是从窗口中获得最大值的方式可以改进。最暴力的手段是直接遍历其中的 k 个值外（时间复杂度 (n-k+1)*k），那有没有什么办法能简化呢？一个简单的办法是设置一个变量维护当前窗口的最大值，当该值弹出时再遍历。能够一定程度上减去部分直接遍历的情况，但对于降序的数组等同于最坏情况。比较高明的手段是通过单调队列，维护队列内队首到队尾降序，答案就取队首。 https://leetcode.cn/problems/sliding-window-maximum/solutions/2499715/shi-pin-yi-ge-shi-pin-miao-dong-dan-diao-ezj6/ 代码解答（强烈建议自行解答后再看）参考题解 12345678910111213141516class Solution: def...

【Leetcode Daily】184设计自助结算系统

题目浅析想查看原题可以点击题目链接。简单地说，就是设计一个类，类中能够存储价格队列，并能随时提取其中最大值，要求加入值，弹出值和取最大值的时间复杂度均为 O(1) 思路分享入队出队对于普通的队列都是 O(1) 复杂度，所以只要解决从队列中提取最大值为 O(1) 复杂度即可。解决这个问题，只要同时引入单调队列维护最大值即可，如果只用一个变量维护最大值，在最坏情况下仍是 O(n) 复杂度。删除队列的元素时，由于单调队列只会降序保存大值，不需要担心顺序错位，毕竟队列按顺序弹值也一定让单调队列按顺序弹值。代码解答（强烈建议自行解答后再看）参考题解 12345678910111213141516171819202122232425262728class Checkout: def __init__(self): self.max_q = deque() self.q = deque() def get_max(self) -> int: return self.max_q[0] if...

【Leetcode Daily】1052爱生气的书店老板

题目浅析想查看原题可以点击题目链接。简单地说，就是给两个整型数组，以及一个整数 minutes，按某个要求（具体看原题，难以简化），求一个数组在另一个数组和 minutes 约束下的求的最大值。思路分享陆爻齐的思路是计算窗口内（也就是冷静的分钟）不满意生气离开的最大值，加上不生气的心情值，再减去所有生气离开的数值得出答案，但由于思想复杂了点，所以略微修改模板结构，也就是下面陆爻齐的答案。参照灵茶山艾府，其实只要区分开两部分相加即可，然后直接参照模板。这两部分，一个是不生气的值，一个是生气下的值，取生气下最大值即可。这样就不用像上面一样多一次运算。 https://leetcode.cn/problems/grumpy-bookstore-owner/solutions/2751888/ding-chang-hua-dong-chuang-kou-fu-ti-dan-rch7/ 代码解答（强烈建议自行解答后再看）陆爻齐的解法 12345678910111213141516171819202122232425class Solution...

数据加载中