題目URL:https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/
題目要求:
思路：因為在連續區間內任意兩個數的差值都要≤ limit,所以 max-min ≤ limit.在一個數組中找滿足該要求的最長連續子數組。可以考慮使用滑動窗口。(滑動窗口在左端固定前提下，右端找到的最長子數組就是題目所求子數組已經被證明過兩次了)
滑動窗口初始 left,right = 0,0
當滑動窗口內，出現了max-min > limit,就是固定右指針。然後不停移動左指針，指到窗口滿足 max-min ≤ limit
right +=1
求區間的最小值，①python中時調用sortedcontainer三方包，利用SortedList來解決。②本地可以使用單調隊列(不能使用單調棧：無法知道各個元素的位置，導致移動左指針時，不能移動左指針索引位的元素)
代碼如下：
class Solution(object):
def longestSubarray(self, nums, limit):
"""
:type nums: List[int]
:type limit: int
:rtype: int
"""
max_len = 0
n = len(nums)
for i in range(n):
for j in range(i, n):
if abs(nums[i] - nums[j]) > limit:
break
max_len = max(max_len, j - i + 1)
return max_len
#創建兩個堆:一個大，一個小。利用max-min + 滑動窗口
import collections
class Solution:
def longestSubarray(self, nums, limit: int) -> int:
max_que, min_que = collections.deque(), collections.deque()
right,left = 0,0
n = len(nums)
max_len = 0
while right < n:
#創建單調隊列
while max_que and max_que[-1] < nums[right]:
max_que.pop()
while min_que and min_que[-1] > nums[right]:
min_que.pop()
max_que.append(nums[right])
min_que.append(nums[right])
while max_que and min_que and abs(max_que[0] - min_que[0]) > limit:
if max_que[0] == nums[left]:
max_que.popleft()
if min_que[0] == nums[left]:
min_que.popleft()
left += 1
max_len = max(max_len, right - left + 1)
right += 1
return max_len
if __name__ == '__main__':
nums = [8, 2, 4, 7]
limit = 4
nums = [10, 1, 2, 4, 7, 2]
limit = 5
nums = [4, 2, 2, 2, 4, 4, 2, 2]
limit = 0
nums = [2,2,5,2,1,3,2,2,2]
limit = 2
print(Solution().longestSubarray(nums, limit))