Leetcode題解 Pythonython：Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

給一串整數陣列 nums 跟整數 limit，求連續子陣列的最大小值相減 <= limit 的最大子陣列個數。

我以前有碰到過這種問題，但我沒有在當下把 deque 的觀念內化，都選擇用dp，終於在今天吃苦頭。
(又或者可以用 two pointers 做解決。)

這種類型的問題有一個特色，就是有「連續子陣列(或串列)」，若條件不合，去掉頭再繼續。

用 時間複雜度 O(N) 解決掉，只給跑一次 nums 的機會。

基本架構是用一個串列，先把遇到的數加進串列後方，(while)若 max() – mix() > limit 則 del[0]，在每輪最後檢查len()。

基本型(Python) ※會超時

class Solution:
    def longestSubarray(self, nums, limit) -> int:
        queue = []
        result = 0
        for i in range(len(nums)):            
            queue.append(nums[i])
            while queue and max(queue) - min(queue) > limit:
                del queue[0]
            result = max(result, len(queue))
        return result

其中最耗費時間的函數是 max() 跟 min() ，如果queue的所含的個數很多，就會在這裡因為一直找而超時。

所以改善這一塊，用兩個變數 maxValue 跟 minValue 去保存最大小值就能順利通過。

改善型(Python)

class Solution:
    def longestSubarray(self, nums, limit) -> int:
        queue = []
        result = 0
        maxValue = minValue = nums[0]
        for i in range(len(nums)):            
            queue.append(nums[i])
            maxValue = max(maxValue, nums[i])
            minValue = min(minValue, nums[i])
            while queue and maxValue - minValue > limit:
                v = queue.pop(0)
                if queue:
                    if v == maxValue: maxValue = max(queue)
                    if v == minValue: minValue = min(queue)
                else:
                    maxValue = nums[i+1]
                    minValue = nums[i+1]
            result = max(result, len(queue))
        return result

class Solution:
    def longestSubarray(self, nums, limit) -> int:
        sp = 0
        result = 0
        maxValues = [] 
        minValues = []
        for i in range(len(nums)):    
            num = nums[i]            
            if not maxValues or num >= maxValues[-1]: maxValues.append(num)
            if not minValues or num <= minValues[-1]: minValues.append(num)
            print(i, sp, maxValues, minValues)

            while maxValues and minValues and i>sp and maxValues[-1] - minValues[-1] > limit:
                v = nums[sp]
                sp += 1
                if v == maxValues[0]: 
                    del maxValues[0]
                    if not maxValues: maxValues.append(max(nums[sp:i+1]))
                if v == minValues[0]: 
                    del minValues[0]
                    if not minValues: minValues.append(min(nums[sp:i+1]))

            result = max(result, i-sp+1)
        return result