2
数据结构之SortedList
source link: https://ivalue2333.github.io/2021/02/22/algorithm/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B9%8BSortedList/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
数据结构之SortedList
[TOC]
SortedList 可以在对数时间内增加或删除一个元素，并且，能在常数时间内获取最大值和最小值，并且其遍历是有序的。
他的实现是使用了分段数组
def sortedListDemo():
# 可以看到是有序的
"""
SortedList 可以在对数时间内增加或删除一个元素，并且，能在常数时间内获取最大值和最小值，并且其遍历是有序的。
:return:
"""
print("-" * 10, "SortedList")
sl = sortedcontainers.SortedList(['e', 'a', 'c', 'd', 'b', 'g'])
print(sl)
print(sl[1])
sl.add('f')
print(sl)
slice1 = [1, 3, 4]
slice1.insert(1, 2)
print(slice1)
for num in sl:
print(num)
1438. 绝对差不超过限制的最长连续子数组
class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
import sortedcontainers
"""
难点：对于任意区间，怎样在logK时间知道最大值和最小值的差值呢！
选用合适的数据结构 SortedList
"""
window = sortedcontainers.SortedList()
left, right = 0, 0
ans = 0
N = len(nums)
while right < N:
window.add(nums[right])
while window[-1] - window[0] > limit:
window.remove(nums[left])
left += 1
ans = max(ans, right-left+1)
right += 1
return ans
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK