滑动窗口最大值：小队从大到小排
窗口每次右端进一个、左端丢一个。队列里只留下标，值从大到小：新数从尾巴踢掉所有更弱的，队首一旦滑出窗口就丢掉。队首永远是当前最大。
双端队列存下标，对应的值单调递减。每步先把队尾所有小于新值的下标弹出并压入新下标，再丢掉已经滑出窗口的队首，队首就是本窗最大值。每个下标进出一次，时间 O(n)，空间 O(k)。
给你一个数组和窗口长度 k。窗口从最左端开始，每次向右滑一格，输出每个窗口里的最大值。窗口始终覆盖连续 k 个数。
主例 nums = [1, 3, -1, -3, 5, 3, 6, 7]，k = 3。六个窗口的最大值依次是 3、3、5、5、6、7。
每个窗口重新扫一遍是 O(n·k)。本文要回答：为什么更小又更靠左的数可以永远丢掉，以及主例里 5 入队时怎样把 3、-1、-3 一次踢光。
更弱且更靠左的，再也当不成最大
第一直觉是每个窗口扫 k 个数找最大。主例 6 个窗口、每个看 3 个数，还能数过来；k 接近 n 时就接近平方。用大顶堆维护窗口，删除滑出去的那个数不方便，还要对数代价。真正重复的劳动是：窗口只变两端，中间那截的大小关系大部分还在。
缺的是一个能在两端修改、并且始终把最大值放在固定一端的结构。双端队列按下标存人，并保持从队首到队尾对应的值递减，队首就是当前窗口最大。新数 x 进来时，队尾所有比 x 小的都可以弹掉：它们既更小又更靠左，以后只要窗口还含着 x，它们都当不成最大。
队首的下标若已经 ≤ i−k，说明它滑出左边界，从队首弹掉。窗口右端第一次走到 k−1 之后，每次都输出队首的值。
为什么必须用双端：踢弱者发生在队尾，踢过期发生在队首，两头都要出队。普通栈只能动顶部，过期的最大值卡在底部拿不出来。队列里存下标而不是存值，是为了用下标判断谁已经离开窗口。
用手走主例。1 入队后，3 把它从队尾踢掉，队列只留下标 1。-1 比 3 小，留在队尾，队列下标 [1,2]，窗口 [1,3,-1] 最大是 3，这是演示第一帧。-3 更小，接到队尾，窗口 [3,-1,-3] 最大仍是 3，队列 [1,2,3]，这是第二帧。5 进来时队尾三个都比它小，全部踢光，队列只留下标 4，窗口最大变成 5，这是第三帧。
后面 3 接到 5 后面，窗口 [-3,5,3] 最大仍是 5；6 把 3 和 5 都踢掉，最大 6；7 再入，最大 7。滑完答案 [3,3,5,5,6,7]。演示收尾窗口落到最后三个数，队列标着后两根柱的下标。每个下标最多进队一次、出队一次，总时间线性。
相等时要不要踢，看实现用的是小于还是小于等于：踢掉相等的旧下标也安全，因为同样的值、更靠右的那个活得更久。不要在队首过期之前就输出，前 k−1 个位置窗口还没满。不要把队列理解成窗口里的全部元素——被踢掉的小数已经不在队列里，但它们可能还在窗口里，只是再也当不成最大。
与单调栈的分工单调栈只在一端进出，适合「下一个更大」。窗口会从左边过期，必须能从另一端把头拿掉，所以用双端队列。递减保证队首是最大，下标保证能判断过期。
Go：双端队列
func maxSlidingWindow(nums []int, k int) []int {q := []int{} // 存下标，值单调递减res := make([]int, 0, len(nums)-k+1)for i, x := range nums {for len(q) > 0 && nums[q[len(q)-1]] < x {q = q[:len(q)-1]}q = append(q, i)if q[0] <= i-k { q = q[1:] }if i >= k-1 {res = append(res, nums[q[0]])}}return res}
1队尾 while 踢的是比 x 小的旧下标。主例 5 进来时，3、-1、-3 连续出队，队列只剩 4。
2q[0] <= i-k 表示队首已经离开左边界。存下标就是为了写这句。
3i >= k-1 窗口才满。主例 i=2 第一次输出 3，最后六个数是 [3,3,5,5,6,7]。
总结
递减双端队列：新的踢更弱的，过期踢队首。主例 [3,3,5,5,6,7]。
- 更小又更靠左的数，只要新数还在窗口里就当不成最大，可以立刻丢掉。
- 主例窗口 [1,3,-1] 和 [3,-1,-3] 最大都是 3；5 入队后队列只留下标 4。
- 两头都要出队，所以用双端不是普通栈。每个下标进出一次。