[TOC]
基础知识
队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。
单调队列不是单纯的给队列中元素排序，那和优先级队列没有什么区别了。
设计单调队列的时候，pop，和push操作要保持如下规则：
pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。
单调队列模板
队列里存数值
type StrictQueue struct {
Queue []int
}
func NewStrictQueue() *StrictQueue {
return &StrictQueue{
Queue: make([]int, 0),
}
}
// 如果队列不为空且要移除的元素为队列中最大值，则将其弹出，否则不做任何操作，因为我们关心的是队列中的最大值
func (sq *StrictQueue) Pop(value int) {
if !sq.IsEmpty() && sq.Queue[0] == value {
sq.Queue = sq.Queue[1:]
}
}
// 如果队列不为空且要添加的元素大于队列入口元素，则将队列入口元素弹出，直到添加的元素小于等于队列入口元素为止，以保证队列是严格单调递减的。
func (sq *StrictQueue) Push(value int) {
for !sq.IsEmpty() && sq.Queue[sq.Size()-1] < value {
sq.Queue = sq.Queue[:sq.Size()-1]
}
sq.Queue = append(sq.Queue, value)
}
// 返回队列中的第一个元素，此处是最大值
func (sq *StrictQueue) Peek() int {
return sq.Queue[0]
}
func (sq *StrictQueue) IsEmpty() bool {
return len(sq.Queue) == 0
}
func (sq *StrictQueue) Size() int {
return len(sq.Queue)
}
队列里存index
type StrictQueue struct {
Queue []int
}
func NewStrictQueue() *StrictQueue {
return &StrictQueue{
Queue: make([]int, 0),
}
}
// peekFirst()方法用于返回此双端队列表示的队列的第一个元素，但不删除该元素。
func (sq *StrictQueue) peekFirst() int {
if !sq.IsEmpty() {
return sq.Queue[0]
}
return -1
}
// peekLast()方法最后一个元素或结尾元素，但不会从列表中删除最后一个元素。
func (sq *StrictQueue) peekLast() int {
if !sq.IsEmpty() {
return sq.Queue[len(sq.Queue)-1]
}
return -1
}
// pollFirst 检索并删除此列表的第一个元素，如果此列表为空，则返回null。
func (sq *StrictQueue) pollFirst() {
if !sq.IsEmpty() {
sq.Queue = sq.Queue[1:]
}
}
// pollLast 检索并删除此列表的最后一个元素，如果此列表为空，则返回null。
func (sq *StrictQueue) pollLast() {
if !sq.IsEmpty() {
sq.Queue = sq.Queue[:len(sq.Queue)-1]
}
}
// offerLast 用于在此Deque的末尾添加特定元素。
func (sq *StrictQueue) offerLast(value int) {
sq.Queue = append(sq.Queue, value)
}
func (sq *StrictQueue) IsEmpty() bool {
return len(sq.Queue) == 0
}
func (sq *StrictQueue) Size() int {
return len(sq.Queue)
}
Leetcode刷题
239. 滑动窗口最大值【困难】
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
输入：nums = [1], k = 1
输出：[1]
// =========================== 解法一：单调队列，队列里存的是数值 =================
//链接：https://leetcode-cn.com/problems/sliding-window-maximum/solution/dai-ma-sui-xiang-lu-dai-ni-gao-ding-zhan-y82r/
func main() {
input := []int{1, 3, -1, -3, 5, 3, 6, 7}
k := 3
fmt.Println(maxSlidingWindow2(input, k))
}
type StrictQueue struct {
Queue []int
}
func NewStrictQueue() *StrictQueue {
return &StrictQueue{
Queue: make([]int, 0),
}
}
// 如果队列不为空且要移除的元素为队列中最大值，则将其弹出，否则不做任何操作，因为我们关心的是队列中的最大值
func (sq *StrictQueue) Pop(value int) {
if !sq.IsEmpty() && sq.Queue[0] == value {
sq.Queue = sq.Queue[1:]
}
}
// 如果队列不为空且要添加的元素大于队列入口元素，则将队列入口元素弹出，直到添加的元素小于等于队列入口元素为止，以保证队列是严格单调递减的。
func (sq *StrictQueue) Push(value int) {
for !sq.IsEmpty() && sq.Queue[sq.Size()-1] < value {
sq.Queue = sq.Queue[:sq.Size()-1]
}
sq.Queue = append(sq.Queue, value)
}
// 返回队列中的第一个元素，此处是最大值
func (sq *StrictQueue) Peek() int {
return sq.Queue[0]
}
func (sq *StrictQueue) IsEmpty() bool {
return len(sq.Queue) == 0
}
func (sq *StrictQueue) Size() int {
return len(sq.Queue)
}
// maxSlidingWindow 时间复杂度O(N), 空间复杂度O(N)
func maxSlidingWindow(nums []int, k int) []int {
var res []int
sq := NewStrictQueue()
for i := 0; i < k; i++ { // 首先将前k个元素添加到队列中
sq.Push(nums[i])
}
fmt.Println(sq.Queue)
res = append(res, sq.Peek()) // 将前k个元素中的最大值添加到结果集合中
for i := k; i < len(nums); i++ {
sq.Pop(nums[i-k]) // // 队列移除最前面元素
//fmt.Println(sq.Queue)
sq.Push(nums[i]) // 向队列添加新元素，也就是当前元素nums[i]
//fmt.Println(sq.Queue)
res = append(res, sq.Peek()) // 将当前队列中的最大值添加到结果集合中
}
return res
}
//================== 解法二 ：单调队列，队列里存的是 index ==================
// B站上古城算法,模板思路是：
// a：去尾操作：队尾元素出队列，如果队列有新元素待入队，需要从队尾开始，删除影响队列单调性的元素，维护队列的单调性。
// b: 去尾操作后，将新元素入列
// c: 删头操作：队头元素出队列，如果队列中总数超了窗口大小了，就要删除队头接着找其他的了，单调队列的队头就是窗口内的极值
// d: 取解操作：取出队头元素，就是窗口内的极值
// 1. index=0 入队列
// 2、num[index=1]>num[index=0],右出queue,即把index=0剔出，保证队列单调递减
// 3、index=1入队列
// 4、idex=2入队列
// 5、已经遍历到index=2，可以找一把最大值了，最大值是queue最左边index对应的数值
// 6、index=3入队列，此时队列里有[1 2 3]
// 7、左出queue，因为k=3,队列里已经有三个index了......
func maxSlidingWindow(nums []int, k int) []int {
lenNum := len(nums)
res := make([]int, 0)
sq2 := NewStrictQueue()
fmt.Println(sq2.Queue)
for i := 0; i < lenNum; i++ {
startWindow := i - k + 1
for !sq2.IsEmpty() && i-sq2.peekFirst() >= k { // 左出queue，保证窗口为k-1
sq2.pollFirst()
fmt.Println(sq2.Queue)
}
for !sq2.IsEmpty() && nums[sq2.peekLast()] <= nums[i] { // 右出queue，保证递减队列
sq2.pollLast()
fmt.Println(sq2.Queue)
}
sq2.offerLast(i) // 进queue，此时queue.size==k
fmt.Println(sq2.Queue)
if startWindow >= 0 {
res = append(res, nums[sq2.peekFirst()]) // 使用queue左边最大值
}
}
return res
}
type StrictQueue struct {
Queue []int
}
func NewStrictQueue() *StrictQueue {
return &StrictQueue{
Queue: make([]int, 0),
}
}
// peekFirst()方法用于返回此双端队列表示的队列的第一个元素，但不删除该元素。
func (sq *StrictQueue) peekFirst() int {
if !sq.IsEmpty() {
return sq.Queue[0]
}
return -1
}
// peekLast()方法最后一个元素或结尾元素，但不会从列表中删除最后一个元素。
func (sq *StrictQueue) peekLast() int {
if !sq.IsEmpty() {
return sq.Queue[len(sq.Queue)-1]
}
return -1
}
// pollFirst 检索并删除此列表的第一个元素，如果此列表为空，则返回null。
func (sq *StrictQueue) pollFirst() {
if !sq.IsEmpty() {
sq.Queue = sq.Queue[1:]
}
}
// pollLast()检索并删除此列表的最后一个元素，如果此列表为空，则返回null。
func (sq *StrictQueue) pollLast() {
if !sq.IsEmpty() {
sq.Queue = sq.Queue[:len(sq.Queue)-1]
}
}
// offerLast用于在此Deque的末尾添加特定元素。
func (sq *StrictQueue) offerLast(value int) {
sq.Queue = append(sq.Queue, value)
}
func (sq *StrictQueue) IsEmpty() bool {
return len(sq.Queue) == 0
}
func (sq *StrictQueue) Size() int {
return len(sq.Queue)
}
862. 和至少为 K 的最短子数组（困难）
给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。子数组 是数组中 连续 的一部分。
输入：nums = [1,2], k = 4
输出：-1
输入：nums = [2,-1,2], k = 3
输出：3
// 维护一个递增的queue.
// 先求出前缀和，排队，对于某个人来说，要找到前面比我矮K的人，而且我和他的位置要最近。
func shortestSubarray(nums []int, k int) int {
len_nums := len(nums)
prefixSum := make([]int, len_nums+1)
prefixSum[0] = 0 // 固定模板，前缀和第0个元素初始化为0
for i := 0; i < len_nums; i++ {
prefixSum[i+1] = prefixSum[i] + nums[i]
}
squeue := NewStrictQueue()
res := math.MaxInt32
for i := 0; i < len_nums+1; i++ {
for !squeue.IsEmpty() && prefixSum[i]-prefixSum[squeue.peekFirst()] >= k {
res = min(res, i-squeue.peekFirst())
//fmt.Println(squeue.Queue)
//fmt.Println(squeue.peekFirst())
squeue.pollFirst()
}
for !squeue.IsEmpty() && prefixSum[squeue.peekLast()] >= prefixSum[i] { //保证是递增队列
squeue.pollLast()
//fmt.Println(squeue.Queue)
}
squeue.offerLast(i)
//fmt.Println(squeue.Queue)
}
if res <= len_nums { // 最后这个没看懂
return res
}
return -1
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
type StrictQueue struct {
Queue []int
}
func NewStrictQueue() *StrictQueue {
return &StrictQueue{
Queue: make([]int, 0),
}
}
// peekFirst()方法用于返回此双端队列表示的队列的第一个元素，但不删除该元素。
func (sq *StrictQueue) peekFirst() int {
if !sq.IsEmpty() {
return sq.Queue[0]
}
return -1
}
// peekLast()方法最后一个元素或结尾元素，但不会从列表中删除最后一个元素。
func (sq *StrictQueue) peekLast() int {
if !sq.IsEmpty() {
return sq.Queue[len(sq.Queue)-1]
}
return -1
}
// pollFirst 检索并删除此列表的第一个元素，如果此列表为空，则返回null。
func (sq *StrictQueue) pollFirst() {
if !sq.IsEmpty() {
sq.Queue = sq.Queue[1:]
}
}
// pollLast 检索并删除此列表的最后一个元素，如果此列表为空，则返回null。
func (sq *StrictQueue) pollLast() {
if !sq.IsEmpty() {
sq.Queue = sq.Queue[:len(sq.Queue)-1]
}
}
// offerLast 用于在此Deque的末尾添加特定元素。
func (sq *StrictQueue) offerLast(value int) {
sq.Queue = append(sq.Queue, value)
}
func (sq *StrictQueue) IsEmpty() bool {
return len(sq.Queue) == 0
}
func (sq *StrictQueue) Size() int {
return len(sq.Queue)
}
网友评论