13-《进阶》单调栈和窗口.md

[TOC]
# 1 单调栈和窗口及其更新结构

## 1.1 窗口

### 1.1.1 滑动窗口是什么？

> 窗口只是我们脑海中的一个范围，用过L和R来规定我们窗口的边界。保证L<=R这个条件

1、滑动窗口是一种想象出来的数据结构；

2、滑动窗口有左边界L和右边界R

3、在数组或者字符串或者一个序列上，记为S,窗口就是S[L...R]这一部分

4、L往右滑动意味着一个样本出了窗口，R往右滑意味着一个样本进了窗口

5、 L和R都只能往右滑动


### 1.1.2 滑动窗口能做什么？

滑动窗口、首尾指针等技巧，说白了就是一种求解问题的流程设计。

### 1.1.3 维护窗口滑动的更新结构

> 例如我们求窗口内最大值问题

> 用单调双端队列来实现，双端队列就是我们的双向链表结构。我们保证我们的双端队列从头部到尾部数值是**从大到小**的

1、 如果窗口的R位置往右移动，我们把进入窗口的这个数从尾部加入到双端队列。如果当前数比该数的前一个数大（从尾部看）那么队列中小于等于的数弹出。直到小于队列的前一个数，加入该数。

2、如果窗口的L位置往右移动，预示着有数要出我们的窗口，我们从双端队列的头部观看要出去的数是不是我们头部队列的数。是就弹出头部的数，不是就不做任何操作

3、我们窗口结构一直被维护，双端队列右边进，左边出。那么窗口的最大值就是我们双端队列最左侧（头部）的值

双端队列结构实质上指的是：如果此时形成的窗口状况，不想让R往右动了，而让L往右动。谁会以此成为最大值的优先级。为什么弹出的数不再找回，原因是在窗口滑动的过程中，被弹出的数的优先级已经被后来的大数取代了，这就是尾端加入，前一个数比当前数小则弹出，比当前数大就加入当前数的道理


> 反之，如果我们要窗口内最小值，只需要维护我们的双端队列单调递增的，既由小到大的即可

复杂度：窗口滑动经过的数，最多进双端队列一次，最多出双端队列一次，如果窗口滑动了N个数，时间复杂度就是O(N)，单次平均O(1)。


### 1.1.4 高频题：求滑动窗口最大值

假设一个固定大小为W的窗口，依次划过arr，返回每一次划出状况的最大值

例如，`arr=[4, 3, 5, 4, 3, 3, 6, 7]`

返回：`[5, 5, 5, 4, 6, 7]`

分析：窗口起始是4,3,5,窗口内最大值是5。窗口向右滑动变为3,5,4最大值5......

```Go
package main

import (
	"container/list"
	"fmt"
)

// getMaxWindow arr 是数据样本 w是窗口大小
func getMaxWindow(arr []int, w int) []int {
	if len(arr) == 0 || w < 1 || len(arr) < w {
		return nil
	}

	// 双向链表
	// 其中放的是下标位置，头代表 （大->小）尾
	qmax := list.List{}
	// 窗口在滑动的过程中，最终会生成arr长度-窗口起始宽度+1个值
	res := make([]int, len(arr) - w + 1)
	index := 0
	// 双端队列的头部元素
	var fe = &list.Element{}
	// 双端队列的尾部元素
	var ee = &list.Element{}
	// L...R
	//     R
	for R := 0; R < len(arr); R++ { // 当前让 i -> [i] 进窗口 ， i 就是 r
		// R 位置的值  可以放在比他大的数后，或者空
		// 双端队列不为空，且双端队列尾部的值小于当前要进入窗口的值
		for qmax.Len() != 0 && arr[qmax.Back().Value.(int)] <= arr[R] {
			// 双端队列从尾部弹出
			qmax.Remove(ee)
			if qmax.Len() > 0 {
				ee = qmax.Back()
				fe = qmax.Front()
			}
		}
		// 经过上述的while，最终把当前进入窗口的数放入双端队列的尾部
		qmax.PushBack(R)
		fe = qmax.Front()
		ee = qmax.Back()
		// 数进来了
		// 如果窗口没有形成W的长度之前，不弹出数字的
		// 当前下标是R, R-W就是需要过期的下标。
		// 如果双端队列的头部保存的下标等于R-W，就头部弹出。实质R-W就是我们原始结构的L下标
		if qmax.Front().Value.(int) == R - w {
			qmax.Remove(fe)
		}

		// 以上窗口更新做完了
		// 窗口没有形成W长度之前，不收集答案。形成W长度后，每一次收集一个答案
		if R >= w -1 {
			res[index] = arr[qmax.Front().Value.(int)]
			index++
		}
	}
	return res
}

func main() {
	arr := []int{4, 3, 5, 4, 3, 3, 6, 7}
	w := 3
	fmt.Println(getMaxWindow(arr, w))
}
```

### 1.1.5 高频题二：达标子数组数量问题

给定一个整形数组arr，和一个整数num。某个arr中的子数组sub，如果想达标，必须满足: sub中最大值-sub中最小值<=num，返回arr中达标子数组的数量

> 子数组是连续的

> 结论1：对于[L,R]范围达标，那么[L,R]上的子数组都达标。max[L...R]肯定比其子数组的max要大，min[L...R]肯定比其范围内的子数组要小，那么[L...R]上满足max - min < num，则其子数组必定满足

> 同理可得结论2：对于[L...R]范围不达标，那么扩展范围后的[L'...R']也不达标

> 我们建立两个双端队列，一个是窗口最大值的双端队列，一个是窗口最小值的双端队列。我们扩展我们的窗口R加1，每扩展一个判断是否仍然达标，达标继续扩展，不达标就停，可以得到本次子数组的达标情况，接着缩小我们的窗口L加1，继续...。窗口滑动不会回退，整体O(N)

```Go
package main

import (
	"container/list"
	"fmt"
)

// 达标子数组数量问题

// getNum 给定样本数组，和一个目标数值num。求arr中达标的子数组，达标的要求为子数组中最大值减去子数组中最小值小于等于num
func getNum(arr []int, num int) int {
	if len(arr) == 0 {
		return 0
	}

	// 窗口内最小值的更新结构
	qmin := list.List{}
	// 窗口内的最大值的更新结构
	qmax := list.List{}

	// 最小值双端队列的头部元素
	var minfe = &list.Element{}
	// 最小值双端队列的尾部元素
	var minee = &list.Element{}

	// 最大值双端队列的头部元素
	var maxfe = &list.Element{}
	// 最小值双端队列的尾部元素
	var maxee = &list.Element{}

	L := 0
	R := 0
	// [L..R) -> [0,0) 窗口内无数 [1,1)
	// [0,1) -> [0~0] 窗口里只有一个数
	res := 0
	// L是开头位置，尝试每一个开头
	for L < len(arr) {
		// 如果此时窗口的开头是L,下面的for工作是:R向右扩到违规为止

		// R是最后一个达标位置的再下一个，通过下文的break终止
		for R < len(arr) {
			// R位置的数进入窗口后，最小值的更新结构和最大值的更新结构都要更新
			for qmin.Len() != 0 && arr[qmin.Back().Value.(int)] >= arr[R] {
				// 尾部移除
				qmin.Remove(minee)
				if qmin.Len() > 0 {
					minfe = qmin.Front()
					minee = qmin.Back()
				}
			}

			qmin.PushBack(R)
			minee = qmin.Back()
			minfe = qmin.Front()

			// R -> arr[R],
			for qmax.Len() != 0 && arr[qmax.Back().Value.(int)] <= arr[R] {
				// 尾部移除
				qmax.Remove(maxee)
				if qmax.Len() > 0 {
					maxfe = qmax.Front()
					maxee = qmax.Back()
				}
			}

			qmax.PushBack(R)
			maxee = qmax.Back()
			maxfe = qmax.Front()

			if arr[qmax.Front().Value.(int)]-arr[qmin.Front().Value.(int)] > num {
				break
			}
			R++
		}
		// R是最后一个达标位置的再下一个，第一个违规的位置
		res += R - L
		// 检查最小值和最大值的更新结构有没有过期
		if qmin.Front().Value.(int) == L {
			qmin.Remove(minfe)
			if qmin.Len() > 0 {
				minfe = qmin.Front()
				minee = qmin.Back()
			}
		}

		if qmax.Front().Value.(int) == L {
			qmax.Remove(maxfe)
			if qmax.Len() > 0 {
				maxfe = qmax.Front()
				maxee = qmax.Back()
			}
		}
		// 窗口左边界向右滑动，窗口容量此时减1
		L++
	}
	return res
}

func main() {
	arr := []int{4, 2, 1, 5, 6, 1, 7, 22, 53, 16, 24, 65, 72, 17, 21, 42}
	num := 5
	fmt.Println(getNum(arr, num))
}
```

> 本题根据窗口滑动建立了单调性，上文的结论

### 1.1.6 如何优化一个问题？

1、 数据状况层面是否可以优化

2、 问题本身是否可以优化。单调性，首尾指针（头指针往右走，尾指针往左走）等

> 遇到一个问题我们先观察，问题本身和范围是否可以建立单调性，至于需要用哪个原型来解决，窗口和首位指针法是常见的流程。所以窗口和首位指针主要用来解决单调性的

## 1.2 单调栈

### 1.2.1 单调栈结构

在一个数组中，求每一个位置左边离它最近的比它小的数在哪，右边离它最近的比它小的数在哪。

例如[3, 2, 1, 7]。3左边比它小的最近的位置的数的位置没有，为-1，右边是1位置的2。2左边比它小的最近的位置的数的位置没有，为-1，右边是2位置的1等。

用一个map来记录，暴力解O(N^2)。单调栈能够在O(N)解决


单调栈算法流程：

> 草稿纸上模拟这个栈;

> 没有相等元素的情况：准备一个栈结构，暂定从小到大的单调栈结构。从左往右遍历我们的数组，[3,4,2,5]，由于栈空，第一个元素可以进栈，3进栈。

> 1位置的数4可以进栈，因为没有破坏从小到大的栈的单调性。

> 2位置的2无法直接进栈，因为会破坏栈的单调性。需要弹出栈元素，元素一旦被弹出，生成相应的记录。

> 1位置的4弹出，右边最近的比你小的数，就是谁让你弹出的数，所以4的右边最近的比4小的数是2。左边最近比你小的数，就是你在栈中压着的数，所以4的左边最近的比4小的数是3。

> 2位置的2此时仍然无法进栈，因为栈中此时还有3，那么3弹出。3的最近的右侧比3小的数是2，3是栈底元素，没有压着的元素，所以3左侧最近的比3小的数没有，位置置为-1。其他元素同理......。

> 最后如果没有元素了，栈中元素弹出，此时不是其他元素迫使的弹出，所以自然弹出的右侧最近比它小的无返回-1。左侧最近比它小的看它在栈中是否压着其他元素

可以选择任意位置去证明，证明略

> 如果存在相等元素的情况，我们栈中每个元素保存为list表示相等元素列表。无法直接进入单调栈时，弹出list最右侧的元素，该元素右侧最近的比自己小的数，就是迫使它弹出的那个数。该元素左侧最近比它小的数，就是自身的这个list压着的的list的最右的数。list的相同元素有两种情况，一种是两个数相等且挨着，另外一种是某个位置释放了中间位置的数后遇到相等元素，进入一个list中去。画栈模拟可看出


```Go
package main

import "fmt"

// 单调栈

// 数组中没有重复值的情况
func getNearLessNoRepeat(arr []int) [][]int {
	res := make([][]int, len(arr))
	for i := 0; i < len(arr); i++ {
		res[i] = make([]int, 2)
	}

	// 模拟一个栈
	stack := make([]int, 0)
	for i := 0; i < len(arr); i++ {
		for len(stack) != 0 && arr[stack[len(stack) - 1]] > arr[i] {
			// 出栈 stack pop
			popIndex := stack[len(stack) - 1]
			stack = stack[:len(stack) - 1]

			leftLessIndex := 0
			if len(stack) == 0 {
				leftLessIndex = -1
			} else {
				leftLessIndex = stack[len(stack) - 1]
			}

			res[popIndex][0] = leftLessIndex
			res[popIndex][1] = i
		}
		// stack push i
		stack = append(stack, i)
	}

	for len(stack) != 0 {
		// 出栈 stack pop
		popIndex := stack[len(stack) - 1]
		stack = stack[:len(stack) - 1]

		leftLessIndex := 0
		if len(stack) == 0 {
			leftLessIndex = -1
		} else {
			// leftLessIndex = stack peek
			leftLessIndex = stack[len(stack) - 1]
		}

		res[popIndex][0] = leftLessIndex
		res[popIndex][1] = -1
	}

	return res
}

// arr [3, 2, 1, 4, 5]
//      0  1  2  3  4

// 表示 0这个数左边最近比0小的没有，位置是-1，右边1。1位置数左边最近比0小的没有-1，右边2
//  [
//    0 :  [-1,  1  ]
//    1 :  [-1,  2  ]

//  ]
// 数组中存在重复值的情况
func getNearLess(arr []int) [][]int {
	res := make([][]int, len(arr))
	for i := 0; i < len(arr); i++ {
		res[i] = make([]int, 2)
	}

	// []int -> 放的是位置，同样值的东西，位置压在一起
	// 代表值    底  ->  顶   小  -> 大
	stack := make([][]int, 0)

	for i := 0; i < len(arr); i++ { // i -> arr[i] 进栈
		// 栈底 -> 栈顶， 小 -> 大
		for len(stack) != 0 && arr[stack[len(stack) - 1][0]] > arr[i] {
			// 出栈 stack pop
			popIs := stack[len(stack) - 1]
			stack = stack[:len(stack) - 1]

			// 取位于下面位置的列表中，最晚加入的那个
			leftLessIndex := 0
			if len(stack) == 0 {
				leftLessIndex = -1
			} else {
				leftLessIndex = stack[len(stack) - 1][len(stack[len(stack) - 1]) - 1]
			}

			for _,popi := range popIs {
				res[popi][0] = leftLessIndex
				res[popi][1] = i
			}
		}

		// 相等的、比你小的
		if len(stack) != 0 && arr[stack[len(stack) - 1][0]] == arr[i] {
			stack[len(stack) - 1] = append(stack[len(stack) - 1], i)
		} else {
			list := make([]int, 0)
			list = append(list, i)
			// stack push
			stack = append(stack, list)
		}
	}

	for len(stack) != 0 {
		// stack pop
		popIs := stack[len(stack) - 1]
		stack = stack[:len(stack) - 1]

		// 取位于下面位置的列表中，最晚加入的那个
		leftLessIndex := 0
		if len(stack) == 0 {
			leftLessIndex = -1
		} else {
			leftLessIndex = stack[len(stack) - 1][len(stack[len(stack) - 1]) - 1]
		}

		for _,popi := range popIs {
			res[popi][0] = leftLessIndex
			res[popi][1] = -1
		}
	}
	return res
}

func main() {
	arr := []int{4, 3, 5, 6, 7}
	fmt.Println(getNearLessNoRepeat(arr))
	arr = []int{4, 3, 5, 4, 3, 3, 6, 7}
	fmt.Println(getNearLess(arr))
}
```

### 1.2.2 单调栈的应用

给定一个只包含正整数的数组arr，arr中任何一个子数组sub，一定都可以算出(sub累加和)*(sub中的最小值)是什么，那么所有子数组中，这个值最大是多少？

```Go
package main

import (
	"fmt"
	"math"
)

// 给定一个正整数数组，求子数组中，累加和乘以数组中最小值。所有子数组中算出的最大值返回
func max1(arr []int) int {
	max := math.MinInt
	for i := 0; i < len(arr); i++ {
		for j := i; j < len(arr); j++ {
			minNum := math.MaxInt
			sum := 0
			for k := i; k <= j; k++ {
				sum += arr[k]
				minNum = int(math.Min(float64(minNum), float64(arr[k])))
			}
			max = int(math.Max(float64(max), float64(minNum * sum)))
		}
	}
	return max
}

func max2(arr []int) int {
	size := len(arr)
	sums := make([]int, size)

	sums[0] = arr[0]
	for i := 1; i < size; i++ {
		sums[i] = sums[i - 1] + arr[i]
	}

	max := math.MinInt
	stack := make([]int, 0)

	for i := 0; i < size; i++ {
		for len(stack) != 0 && arr[stack[len(stack) - 1]] >= arr[i] {
			// stack pop
			j := stack[len(stack) - 1]
			stack = stack[:len(stack) - 1]

			m := math.MinInt
			if len(stack) == 0 {
				m = sums[i - 1]
			} else {
				m = sums[i - 1] - sums[stack[len(stack) - 1]]
			}

			max = int(math.Max(float64(max), float64(m * arr[j])))
		}
		stack = append(stack, i)
	}

	for len(stack) != 0 {
		j := stack[len(stack) - 1]
		stack = stack[:len(stack) - 1]

		m := math.MinInt
		if len(stack) == 0 {
			m = sums[size - 1]
		} else {
			m = sums[size - 1] - sums[stack[len(stack) - 1]]
		}

		max = int(math.Max(float64(max), float64(m * arr[j])))
	}

	return max
}

func main() {
	arr := []int{3, 4, 1, 7, 3, 9, 12, 62, 82, 91, 30}
	fmt.Println(max1(arr))
	fmt.Println(max2(arr))
}
```