前面三个都是滑动窗口问题,后面是第三道题的大小顶堆的解法(第二题和第三题我做出来了)题解还是看这里:https://leetcode-cn.com/
from collections import deque
# 1438. 绝对差不超过限制的最长连续子数组
class Solution(object):
def longestSubarray1(self, nums, limit):
"""
:type nums: List[int]
:type limit: int
:rtype: int
"""
length = len(nums)
if length <= 1:
return length
q = list()
q.append(nums[0])
index = 1
count = float("-inf")
while q and index < length:
new_q = []
q_len = len(q)
flag = False
for i in range(q_len):
# 超界了,就将i之后的赋值给new_q
if i < q_len - 1 and abs(q[i] - nums[index]) > limit:
new_q = q[i+1:]
flag = True
if i == q_len - 1 and abs(q[i] - nums[index]) > limit:
new_q = []
flag = True
if flag:
new_q.append(nums[index])
q = new_q[:]
else:
q.append(nums[index])
count = max(count, len(q))
if len(q) >= 17:
print(q)
index += 1
return count
def longestSubarray2(self, nums, limit: int) -> int:
s = list()
n = len(nums)
left = right = ret = 0
while right < n:
s.append(nums[right])
s = sorted(s)
while s[-1] - s[0] > limit:
s.remove(nums[left])
left += 1
ret = max(ret, right - left + 1)
right += 1
return ret
def longestSubarray3(self, nums, limit: int) -> int:
n = len(nums)
queMax, queMin = deque(), deque()
left = right = ret = 0
while right < n:
while queMax and queMax[-1] < nums[right]:
queMax.pop()
while queMin and queMin[-1] > nums[right]:
queMin.pop()
queMax.append(nums[right])
queMin.append(nums[right])
while queMax and queMin and queMax[0] - queMin[0] > limit:
if nums[left] == queMin[0]:
queMin.popleft()
if nums[left] == queMax[0]:
queMax.popleft()
left += 1
ret = max(ret, right - left + 1)
right += 1
return ret
if __name__ == ‘__main__‘:
nums = [4, 2, 2, 2, 4, 4, 2, 2]; limit = 0
nums = [10, 1, 2, 4, 7, 2]; limit = 5
s1 = Solution()
root = s1.longestSubarray(nums, limit)
print(root)
import bisect
# 1004. 最大连续1的个数 III
class Solution(object):
def longestOnes1(self, A, K):
"""
:type A: List[int]
:type K: int
:rtype: int
"""
left = right = ret = 0
count_0 = 0
length = len(A)
while right < length:
if A[right] == 0:
count_0 += 1
while count_0 > K:
if A[left] == 0:
count_0 -= 1
left += 1
ret = max(ret, right - left + 1)
right += 1
return ret
def longestOnes2(self, A, K):
"""
:type A: List[int]
:type K: int
:rtype: int
"""
left = right = ret = 0
count_0 = 0
length = len(A)
while right < length:
if A[right] == 0:
count_0 += 1
if count_0 > K:
if A[left] == 0:
count_0 -= 1
left += 1
ret = max(ret, right - left + 1)
right += 1
return ret
def longestOnes(self, A, K):
n = len(A)
P = [0]
for num in A:
# 二分法计算前缀数组
P.append(P[-1] + (1 - num))
ans = 0
for right in range(n):
left = bisect.bisect_left(P, P[right + 1] - K)
ans = max(ans, right - left + 1)
return ans
if __name__ == ‘__main__‘:
A = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0];
K = 2
A = [0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1];
K = 3
# A = [1, 1, 0, 0, 0];
# K = 0
s1 = Solution()
root = s1.longestOnes(A, K)
print(root)
# 480. 滑动窗口中位数
from sortedcontainers import SortedList
from bisect import bisect_left
class Solution(object):
def medianSlidingWindow1(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[float]
"""
left = 0
right = k
length = len(nums)
ret_list = []
mid_list = SortedList()
key = (k-1)//2
while right <= length:
mid_list.update(nums[left: right])
# 判断奇偶
if k & 1 == 1:
mid_value = mid_list[key]
else:
mid_value = (mid_list[key] + mid_list[key + 1]) / 2
right += 1
left += 1
ret_list.append(mid_value)
mid_list.clear()
return ret_list
def medianSlidingWindow2(self, nums, k: int):
n = len(nums)
window = []
ans = []
for i in range(n):
idx = bisect_left(window, nums[i])
window[idx:idx] = [nums[i]]
if len(window) > k:
q = nums[i - k]
idx = bisect_left(window, q)
window[idx: idx + 1] = []
if len(window) == k:
median = (window[k // 2] + window[(k - 1) // 2]) / 2
ans.append(median)
return ans
def medianSlidingWindow3(self, a, k: int):
ans = []
for i in range(0, len(a) - k + 1):
ls = a[i: i + k]
ls.sort()
if (k % 2): # 奇数
ans.append(ls[k // 2])
else: # 偶数
ans.append((ls[k // 2 - 1] + ls[k // 2]) / 2)
return ans
def medianSlidingWindow(self, nums, k: int):
# 使用python内置的二分法库
cur = sorted(nums[:k])
def get_mid():
return (cur[(k-1) // 2] + cur[k // 2]) / 2
ret = [get_mid()]
for i in range(k, len(nums)):
cur.insert(bisect_left(cur, nums[i]), nums[i])
cur.pop(bisect_left(cur, nums[i - k]))
ret.append(get_mid())
return ret
if __name__ == ‘__main__‘:
nums = [1, 3, -1, -3, 5, 3, 6, 7]; k = 3
s1 = Solution()
root = s1.medianSlidingWindow(nums, k)
print(root)
import heapq
import collections
class Heap:
def __init__(self, name="min"):
self.arr = []
self.f = lambda x: x if name == "min" else -x
def push(self, num):
heapq.heappush(self.arr, self.f(num)) # 推入一个
def pop(self):
return self.f(heapq.heappop(self.arr)) # 弹出堆顶
def top(self):
return self.f(self.arr[0])
def empty(self):
return len(self.arr) == 0
class Solution:
def medianSlidingWindow(self, nums, k: int):
small = Heap(name="max") # 较小数字部分使用大根堆
big = Heap(name="min") # 较大数字部分使用小根堆
get_mid = lambda x, y: x.top() if k % 2 else (x.top() + y.top()) / 2
mp = collections.defaultdict(int)
for i in range(k):
small.push(nums[i])
for i in range(k//2):
big.push(small.pop())
ans = [get_mid(small, big)]
for i in range(k, len(nums)):
balance = 0
l, r = nums[i-k], nums[i] # 将被删除的窗口最左元素和将被添加到窗口最右的元素
mp[l] += 1 # 左窗口元素记账
if l <= small.top():
balance -= 1 # 较小数字堆需删除一个元素
else:
balance += 1 # 较大数字堆需删除一个元素
if r <= small.top():
balance += 1 # 较小数字堆添加一个元素
small.push(r)
else:
balance -= 1 # 较大数字堆添加一个元素
big.push(r)
"""
此时balance取值可能是:
balance | small | big | 解释
0 | -1+1 | | 较小数字堆删除一个元素添加一个元素，两边还是平衡的
0 | | +1-1 | 较大数字堆删除一个元素添加一个元素，两边还是平衡的
-2 | -1 | -1 | 较小数字堆删除一个元素，较大数字堆添加一个元素，失衡
2 | +1 | +1 | 较大数字堆删除一个元素，较小数字堆添加一个元素，失衡
"""
# 较小数字堆挪一个给较大数字堆(3,3)->(4,2)->(3,3)或者(4,3)->(5,2)->(4,3)
if balance == 2:
big.push(small.pop())
# 较大数字堆挪一个给较小数字堆(3,3)->(2,4)->(3,3)或者(4,3)->(3,4)->(4,3)
if balance == -2:
small.push(big.pop())
# 重新达到平衡了,该看看堆顶是不是待删除元素了
while not small.empty() and mp[small.top()]:
mp[small.top()] -= 1
small.pop()
while not big.empty() and mp[big.top()]:
mp[big.top()] -= 1
big.pop()
# 为什么删除堆顶元素后不用重新平衡两边堆了呢？
ans.append(get_mid(small, big))
return ans
if __name__ == ‘__main__‘:
nums = [1, 3, -1, -3, 5, 3, 6, 7]; k = 3
s1 = Solution()
s1.medianSlidingWindow(nums, k)
原文：https://www.cnblogs.com/liuzhanghao/p/14431144.html