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

Categories:

题目描述
思路分析
1. 解法一：滑动窗口 + 双端队列（推荐）
相似题目

题目描述

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

思路分析

解法一：滑动窗口 + 双端队列（推荐）

核心思路：

用单调队列维护当前窗口的最大值与最小值。

若 max - min > limit，移动左指针缩小窗口。

记录窗口最大长度。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)，双端队列占用线性空间。

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> maxDeque = new ArrayDeque<>();
        Deque<Integer> minDeque = new ArrayDeque<>();
        int left = 0;
        int ans = 0;

        for (int right = 0; right < nums.length; right++) {
            int v = nums[right];

            while (!maxDeque.isEmpty() && nums[maxDeque.peekLast()] < v) {
                maxDeque.pollLast();
            }
            while (!minDeque.isEmpty() && nums[minDeque.peekLast()] > v) {
                minDeque.pollLast();
            }

            maxDeque.addLast(right);
            minDeque.addLast(right);

            while (nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > limit) {
                if (maxDeque.peekFirst() == left) {
                    maxDeque.pollFirst();
                }
                if (minDeque.peekFirst() == left) {
                    minDeque.pollFirst();
                }
                left++;
            }

            ans = Math.max(ans, right - left + 1);
        }

        return ans;
    }
}

func longestSubarray(nums []int, limit int) int {
	maxDeque := make([]int, 0)
	minDeque := make([]int, 0)
	left := 0
	ans := 0

	for right, v := range nums {
		for len(maxDeque) > 0 && nums[maxDeque[len(maxDeque)-1]] < v {
			maxDeque = maxDeque[:len(maxDeque)-1]
		}
		for len(minDeque) > 0 && nums[minDeque[len(minDeque)-1]] > v {
			minDeque = minDeque[:len(minDeque)-1]
		}

		maxDeque = append(maxDeque, right)
		minDeque = append(minDeque, right)

		for nums[maxDeque[0]]-nums[minDeque[0]] > limit {
			if maxDeque[0] == left {
				maxDeque = maxDeque[1:]
			}
			if minDeque[0] == left {
				minDeque = minDeque[1:]
			}
			left++
		}

		if right-left+1 > ans {
			ans = right - left + 1
		}
	}

	return ans
}

相似题目

题目	难度	考察点
239. 滑动窗口最大值	困难	单调队列
1438. 绝对差不超过限制的最长连续子数组	中等	滑动窗口
1004. 最大连续1的个数 III	中等	滑动窗口
424. 替换后的最长重复字符	中等	滑动窗口
862. 和至少为 K 的最短子数组	困难	双端队列

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/60256979