239. Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Example 2:

1
2
Input: nums = [1], k = 1
Output: [1]

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

暴力破解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    res = []  # 存储每个窗口的最大值
    
    # 遍历所有可能的窗口（窗口的右边界从 k-1 开始，直到数组末尾）
    for i in range(k-1, len(nums)):
        j = i - k + 1  # 计算当前窗口的左边界 j
        
        max_val = nums[j]  # 初始化当前窗口的最大值为窗口的第一个元素
        
        # 遍历窗口内的所有元素，寻找最大值
        for l in range(j, i+1):
            max_val = max(max_val, nums[l])  # 更新最大值
        
        res.append(max_val)  # 将当前窗口的最大值加入结果列表
    
    return res  # 返回所有窗口的最大值

Time: O(Nk)
Space: O(1) not including the output array

优先队列/堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import heapq

def maxSlidingWindow(nums, k):
    if not nums:
        return []
    
    res = []
    max_heap = []
    
    for i, num in enumerate(nums):
        # 将当前元素推入堆（Python 默认最小堆，用负数模拟最大堆）
        heapq.heappush(max_heap, (-num, i))
        
        # 当窗口形成后（i >= k-1），开始计算窗口最大值
        if i >= k - 1:
            # 移除堆顶中超出窗口范围的元素（延迟删除）
            while max_heap[0][1] <= i - k:
                heapq.heappop(max_heap)
            
            # 当前堆顶元素（取负数还原）即为窗口最大值
            res.append(-max_heap[0][0])
    
    return res

Time: O(Nk) (if we implement PQ by ourselves, it is O(N\log{k}))
Space: O(k)

单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import deque

def maxSlidingWindow(nums, k):
    res = []
    que = deque()  # 存储索引，保证 nums[que[i]] 单调递减
    
    for i in range(len(nums)):
        # 移除比当前元素小的所有元素（它们不可能是最大值）
        while que and nums[i] >= nums[que[-1]]:
            que.pop()
        que.append(i)
        
        # 移除超出窗口范围的元素
        if que[0] == i - k:
            que.popleft()
        
        # 当窗口形成后（i >= k-1），记录最大值
        if i >= k - 1:
            res.append(nums[que[0]])
 
    return res

Time: O(N) since each element is processed (add/remove) at most twice.
Space: O(k)

线段树

线段树是一棵完全二叉树（所有叶子节点都在最底层），每个节点存储一个区间的统计信息（如最大值、最小值、和等）。

示例：数组 [1, 3, -1, -3] 的线段树（求最大值）

1
2
3
4
5
            [0,3] max=3
           /       \
    [0,1] max=3    [2,3] max=-1
     /    \         /    \
[0] max=1 [1] max=3 [2] max=-1 [3] max=-3
  • 叶子节点：存储单个元素（如 [0] 存 1）
  • 非叶子节点：存储子区间的最大值（如 [0,1] 存 max(1,3)=3）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1  # 最小 2 的幂 >=n
        
        # 分配 2*size 的数组（实际用 2n-1 个节点，多出的空间不用）
        self.tree = [float('-inf')] * (2 * self.size)
        
        # 填充叶子节点（位置 size 到 size+n-1）
        for i in range(self.n):
            self.tree[self.size + i] = data[i]
        
        # 自底向上计算内部节点（位置 1 到 size-1）
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = max(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):
        res = float('-inf')
        l += self.size  # 定位到叶子节点
        r += self.size
        while l <= r:
            if l % 2 == 1:  # 左边界是右孩子，单独处理
                res = max(res, self.tree[l])
                l += 1
            if r % 2 == 0:  # 右边界是左孩子，单独处理
                res = max(res, self.tree[r])
                r -= 1
            l //= 2  # 移动到父节点
            r //= 2
        return res
    
    def update(self, i, value):
        i += self.size  # 找到叶子节点
        self.tree[i] = value
        
        # 向上更新父节点
        while i > 1:
            i //= 2
            self.tree[i] = max(self.tree[2 * i], self.tree[2 * i + 1])
class Solution:
    

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums:
            return []
        
        st = SegmentTree(nums)
        res = []
        for i in range(len(nums) - k + 1):
            res.append(st.query(i, i + k - 1))
        return res

Time: O(NlogN)
Space: O(NlogN)

稀疏表

定义稀疏表 st

  • st[j][i] 表示从位置 i 开始，长度为 2^j的区间的最值。

  • 例如：

    • st[0][i] = nums[i]（长度为 20=120=1 的区间就是元素本身）。
    • st[1][i] = max(nums[i], nums[i+1])（长度为 21=221=2 的区间）。
    • st[2][i] = max(nums[i], nums[i+1], nums[i+2], nums[i+3])（长度为 2^2=4 的区间）

    稀疏表的预处理通过动态规划（DP）完成：

    st[j][i]=max(st[j−1][i],st[j−1][i+2j−1])

    即：区间 [i, i+2^j-1] 的最值 = 左半区间 [i, i+2^{j-1}-1] 和右半区间 [i+2^{j-1}, i+2^j-1] 的最值的较大者。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import math

class SparseTable:
    def __init__(self, nums):
        self.n = len(nums)
        self.k = math.floor(math.log2(self.n)) + 1 if self.n > 0 else 0
        self.st = [[0] * self.k for _ in range(self.n)]
        
        # 初始化
        for i in range(self.n):
            self.st[i][0] = nums[i]
        
        # 动态规划预处理
        for j in range(1, self.k):
            for i in range(self.n - (1 << j) + 1):
                self.st[i][j] = max(self.st[i][j-1], self.st[i + (1 << (j-1))][j-1])
    
    def query(self, l, r):
        length = r - l + 1
        k = math.floor(math.log2(length))
        return max(self.st[l][k], self.st[r - (1 << k) + 1][k])

def maxSlidingWindow(nums, k):
    if not nums:
        return []
    
    st = SparseTable(nums)
    res = []
    for i in range(len(nums) - k + 1):
        res.append(st.query(i, i + k - 1))
    return res

Time: O(NlogN)
Space: O(N)

动态规划

img

动态规划解法将数组分成若干块，预处理每个块从左到右和从右到左的最大值，然后组合结果。

分块预处理：

  • left_max[i]：从当前块的起始位置到 i 的最大值。
  • right_max[i]：从 i 到当前块结束位置的最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        left_max = [0] * n
        right_max = [0] * n

        for i in range(n):
            j = n-1-i
            # 从左到右计算块内最大值
            if i % k == 0:
                left_max[i] = nums[i]
            else:
                left_max[i] = max(left_max[i-1], nums[i])
            # 从右到左计算块内最大值
            if j == n - 1 or (j + 1) % k == 0:
                right_max[j] = nums[j]
            else:
                right_max[j] = max(right_max[j+1], nums[j])

        # 计算每个窗口的最大值
        res = []
        for i in range(n - k + 1):
            j = i + k - 1
            res.append(max(right_max[i], left_max[j]))
        return res

Time: O(N)
Space: O(N)

2373 Largest Local Values in a Matrix

You are given an n x n integer matrix grid.

Generate an integer matrix maxLocal of size (n - 2) x (n - 2) such that:

  • maxLocal[i][j] is equal to the largest value of the 3 x 3 matrix in grid centered around row i + 1 and column j + 1.

In other words, we want to find the largest value in every contiguous 3 x 3 matrix in grid.

Return the generated matrix.

Example 1:

img

1
2
3
4
Input: grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]
Output: [[9,9],[8,6]]
Explanation: The diagram above shows the original matrix and the generated matrix.
Notice that each value in the generated matrix corresponds to the largest value of a contiguous 3 x 3 matrix in grid.

Example 2:

img

1
2
3
Input: grid = [[1,1,1,1,1],[1,1,1,1,1],[1,1,2,1,1],[1,1,1,1,1],[1,1,1,1,1]]
Output: [[2,2,2],[2,2,2],[2,2,2]]
Explanation: Notice that the 2 is contained within every contiguous 3 x 3 matrix in grid.

Constraints:

  • n == grid.length == grid[i].length
  • 3 <= n <= 100
  • 1 <= grid[i][j] <= 100

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def cal_max(self,grid,x,y):
    mx=0
    for i in range(x,x+3):
        for j in range(y,y+3):
            mx = max(mx,grid[i][j])
    return mx

def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
    N = len(grid)
    res = [[0]*(N-2) for _ in range(N-2)]
    for i in range(N-2):
        for j in range(N-2):
            res[i][j] = self.cal_max(grid,i,j)
    return res

单调队列

image.png

image.png

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        res = [[0]*(n-2) for _ in range(n-2)]
        for i in range(n):
            que = deque()
            for j in range(n):
                while len(que)!=0 and grid[i][j]>grid[i][que[-1]]:
                    que.pop()
                que.append(j)
                if j>=2:
                    val = grid[i][que[0]]
                    for k in range(i-2,i+1):
                        if k >= 0 and k < n - 2:
                            res[k][j-2] = max(res[k][j-2],val)
                    if que[0] <= j-2:
                        que.popleft()
        return res

2444. Count Subarrays With Fixed Bounds

Hint

You are given an integer array nums and two integers minK and maxK.

A fixed-bound subarray of nums is a subarray that satisfies the following conditions:

  • The minimum value in the subarray is equal to minK.
  • The maximum value in the subarray is equal to maxK.

Return the number of fixed-bound subarrays.

A subarray is a contiguous part of an array.

Example 1:

1
2
3
Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Output: 2
Explanation: The fixed-bound subarrays are [1,3,5] and [1,3,5,2].

Example 2:

1
2
3
Input: nums = [1,1,1,1], minK = 1, maxK = 1
Output: 10
Explanation: Every subarray of nums is a fixed-bound subarray. There are 10 possible subarrays.

Constraints:

  • 2 <= nums.length <= 105
  • 1 <= nums[i], minK, maxK <= 106

暴力

1
2
3
4
5
6
7
8
9
10
11
def countSubarrays(self, nums, minK, maxK):
    count = 0
    for i in range(len(nums)):
        mini = float('inf')
        maxi = float('-inf')
        for j in range(i, len(nums)):
            mini = min(mini, nums[j])
            maxi = max(maxi, nums[j])
            if mini == minK and maxi == maxK:
                count += 1
    return count

Time: O(N^2)

Space: O(1)

单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        res = 0
        left = 0
        q_min = deque()
        q_max = deque()
        for i in range(len(nums)):
            if not minK<=nums[i]<=maxK:
                q_min.clear()
                q_max.clear()
                left = i+1
                continue
            while q_max and nums[i]>=nums[q_max[-1]]:
                q_max.pop()
            q_max.append(i)
            while q_min and nums[i]<=nums[q_min[-1]]:
                q_min.pop()
            q_min.append(i)
            if nums[q_min[0]] == minK and nums[q_max[0]] == maxK:
                res+=min(q_min[0],q_max[0])-left+1
        return res

Time: O(N)
Space: O(N)

滑动窗口

感觉像单调队列的一种特殊情况

1
2
3
4
5
6
7
8
9
def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
    res = 0
    jbad = jmax = jmin = -1
    for i,a in enumerate(nums):
        if a > maxK or a < minK: jbad=i //if not minK<=a<=maxK
        if a == minK: jmin = i
        if a == maxK: jmax = i
        res += max(0,min(jmax,jmin)-jbad)
    return res

Time: O(N)
Space: O(1)

2762. Continuous Subarrays

You are given a 0-indexed integer array nums. A subarray of nums is called continuous if:

  • Let i, i + 1, …, j be the indices in the subarray. Then, for each pair of indices i <= i1, i2 <= j, 0 <= |nums[i1] - nums[i2]| <= 2.

Return the total number of continuous subarrays.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

1
2
3
4
5
6
7
8
9
Input: nums = [5,4,2,4]
Output: 8
Explanation: 
Continuous subarray of size 1: [5], [4], [2], [4].
Continuous subarray of size 2: [5,4], [4,2], [2,4].
Continuous subarray of size 3: [4,2,4].
There are no subarrys of size 4.
Total continuous subarrays = 4 + 3 + 1 = 8.
It can be shown that there are no more continuous subarrays.

Example 2:

1
2
3
4
5
6
7
Input: nums = [1,2,3]
Output: 6
Explanation: 
Continuous subarray of size 1: [1], [2], [3].
Continuous subarray of size 2: [1,2], [2,3].
Continuous subarray of size 3: [1,2,3].
Total continuous subarrays = 3 + 2 + 1 = 6.

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

有序集合

1
2
3
4
5
6
7
8
9
10
11
12
13
def continuousSubarrays(self, nums: List[int]) -> int:
       ans = left = 0
       cnt = Counter()
       for right, x in enumerate(nums):
           cnt[x] += 1
           while max(cnt) - min(cnt) > 2:
               y = nums[left]
               cnt[y] -= 1
               if cnt[y] == 0:
                   del cnt[y]
               left += 1
           ans += right - left + 1
       return ans

Time: O(Nlogk)

Space: O(K)

堆

原理和单调队列差不多，但是单调队列自维护了单调递增、递减的顺序，因此效率率低于单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def continuousSubarrays(self, nums: List[int]) -> int:
        res = 0
        left = 0
        max_heap = []
        min_heap = []
        for right,num in enumerate(nums):
            heapq.heappush(max_heap,(-num,right))
            heapq.heappush(min_heap,(num,right))
            while left <= right and -max_heap[0][0] - min_heap[0][0] > 2:
                while max_heap and max_heap[0][1] <= left:
                        heapq.heappop(max_heap)
                while min_heap and min_heap[0][1] <= left:
                    heapq.heappop(min_heap)
                left+=1
                
            res+=right-left+1
        return res

Time: O(NlogN)
Space: O(N)

单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def continuousSubarrays(self, nums: List[int]) -> int:
        res = 0
        left = 0  # 窗口左边界
        q_min = deque()  # 单调递增队列，维护最小值
        q_max = deque()  # 单调递减队列，维护最大值

        for i in range(len(nums)):
            # 维护 q_max（单调递减）
            while q_max and nums[i] > nums[q_max[-1]]:
                q_max.pop()
            q_max.append(i)
            
            # 维护 q_min（单调递增）
            while q_min and nums[i] < nums[q_min[-1]]:
                q_min.pop()
            q_min.append(i)
            
            # 如果当前窗口的 max - min > 2，移动左边界 left
            while nums[q_max[0]] - nums[q_min[0]] > 2:
                if q_max[0] == left:
                    q_max.popleft()
                if q_min[0] == left:
                    q_min.popleft()
                left += 1
            
            # 以 nums[i] 结尾的满足条件的子数组数量 = i - left + 1
            res += i - left + 1
        return res

Time: O(N)
Space: O(N)

1438.Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

Example 2:

1
2
3
Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4 
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.

Example 3:

1
2
Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 0 <= limit <= 109

单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def longestSubarray(self, nums: List[int], limit: int) -> int:
        res = 0
        q_max = deque()
        q_min = deque()
        left = 0
        for right,num in enumerate(nums):
            while q_max and num>=nums[q_max[-1]]:
                q_max.pop()
            q_max.append(right)
            while q_min and num<=nums[q_min[-1]]:
                q_min.pop()
            q_min.append(right)
            while nums[q_max[0]] - nums[q_min[0]]>limit:
                left+=1
                if q_max[0]<left:
                    q_max.popleft()
                if q_min[0]<left:
                    q_min.popleft()
            res=max(res,right-left+1)
        return res

Time O(N)
Space O(N)

1425. Constrained Subsequence Sum

Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence of that array such that for every two consecutive integers in the subsequence, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.

A subsequence of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

Example 1:

1
2
3
Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

Example 2:

1
2
3
Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subsequence must be non-empty, so we choose the largest number.

Example 3:

1
2
3
Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subsequence is [10, -2, -5, 20].

动态规划 oot

1
2
3
4
5
6
7
8
9
10
11
12
13
def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
    n = len(nums)
    dp = nums.copy()
    res = dp[0]

    for i in range(1, n):
        # 取前k个元素中的最大值，确保不越界
        start = max(0, i - k)
        max_prev = max(dp[start:i], default=0)
        dp[i] += max(max_prev, 0)
        res = max(res, dp[i])

    return res

单调栈优化DP

1
2
3
4
5
6
7
8
9
10
11
12
def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
    dp = nums.copy()
    q = deque()
    for i in range(len(nums)):    
        while q and q[0]<i-k:
            q.popleft()
        dp[i] += max(0,dp[q[0]] if q else 0)
        while q and dp[q[-1]]<dp[i]:
            q.pop()
        q.append(i)

    print(max(dp))