剑指 Offer 59 - II. 滑动窗口的最大值

剑指 Offer 59 - II. 队列的最大值

https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/

类似与最小栈，首先为了实现队列的功能要维护一个普通的队列，而在最大元素出队时需要知道第二大的元素，因此还需要维护一个 非严格递减 的单调队列。

如果进来了一个较大的元素，由于先进队的元素会先出队，则前面所有比它小的元素都不可能是最大值，可以直接将它们删除而不影响结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
type MaxQueue struct {
    queue []int
    descQ []int  // 非严格递减队列
}


func Constructor() MaxQueue {
    return MaxQueue{make([]int, 0), make([]int, 0)}
}


func (this *MaxQueue) Max_value() int {
    n := len(this.descQ)
    if n == 0 {
        return -1
    }
    return this.descQ[0]
}


func (this *MaxQueue) Push_back(value int)  {
    this.queue = append(this.queue, value)

    // 将单调队列中比新值大的元素都踢出
    for len(this.descQ) > 0 && this.descQ[len(this.descQ)-1] < value {
            this.descQ = this.descQ[:len(this.descQ)-1]
    }
    this.descQ = append(this.descQ, value)
}


func (this *MaxQueue) Pop_front() int {
    if len(this.queue) == 0 {
        return -1
    }

    res := this.queue[0]
    this.queue = this.queue[1:]

    if len(this.descQ) > 0 && res == this.descQ[0] {
        this.descQ = this.descQ[1:]
    }
    return res
}