题目： 有一个整型数组arr，和一个大小为window_size的窗口从数组最左边滑到最右边，每次滑动一个位置。求窗口滑动过程中，窗口中的最大值。
思路： 维护一个双端队列dq，队列中存放的是窗口中最大值的索引的更新结构。 遍历数组arr，当遍历到任意位置i时， 1）若dq为空，直接把下标i放入队列； 2）若dq不空，假设队尾下表j，因为dq维护的是窗口中最大值索引的更新结构，若arr[j] > arr[i]，需要把i放到队尾，因为随着窗口滑动，i滑出窗口时，需要知道后面的最大值；若arr[j] <= arr[i]，说明窗口中出现来更大的值，需要把比arr[i]小的这些移出队列； 3）若队头记录的索引已滑出窗口，需要出队；
代码：
import random from collections import deque def max_value_in_window(arr, window_size): dq = deque() result = [] if arr is None or len(arr) < window_size or window_size < 1: return result for i in range(len(arr)): x = arr[i] while len(dq) != 0 and arr[dq[-1]] <= x: dq.pop() dq.append(i) if dq[0] == i - window_size: dq.popleft() if i >= window_size - 1: result.append(arr[dq[0]]) return result测试：
def test(count, maxnum, window_size): arr = [] for _ in range(count): v = random.randint(0, maxnum) arr.append(v) result = max_value_in_window(arr, window_size) if len(result) != len(arr) - window_size + 1: raise Exception('Error result length') for i in range(len(result)): m = max(arr[i : i+window_size]) if result[i] != m: raise Exception('Error result') if __name__ == '__main__': test(100, 1000, 4) test(1000, 10000, 40) test(10000, 100000, 400) test(10000, 1000, 40)