golang刷leetcode技巧之如何實(shí)現(xiàn)隊(duì)列的最大值

這篇文章主要介紹了golang刷leetcode技巧之如何實(shí)現(xiàn)隊(duì)列的最大值，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

請(qǐng)定義一個(gè)隊(duì)列并實(shí)現(xiàn)函數(shù) max_value 得到隊(duì)列里的最大值，要求函數(shù)max_value、push_back 和 pop_front 的時(shí)間復(fù)雜度都是O(1)。

若隊(duì)列為空，pop_front 和 max_value 需要返回 -1

示例 1：

輸入: 

["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]

[[],[1],[2],[],[],[]]

輸出: [null,null,null,2,1,2]

示例 2：

輸入: 

["MaxQueue","pop_front","max_value"]

[[],[],[]]

輸出: [null,-1,-1]

限制：

1 <= push_back,pop_front,max_value的總操作數(shù) <= 10000

1 <= value <= 10^5

解題思路：

1，對(duì)于先進(jìn)先出，O（1）,顯然是一個(gè)基本的隊(duì)列可以搞定

2，但是實(shí)現(xiàn)O（1）的max，需要優(yōu)先隊(duì)列

3，但是本題的技巧在于:優(yōu)先隊(duì)列只需要按照插入順序，保留前幾個(gè)

4，具體原因：

A，如果插入元素比現(xiàn)在優(yōu)先隊(duì)列元素都小，插入隊(duì)尾即可，這很好理解

B，如果插入元素A比現(xiàn)在優(yōu)先隊(duì)列某些元素a,b,c大，那么，a,b,c 出隊(duì)的時(shí)候,最大元素肯定大于等于A，所以，沒有必要維護(hù)a,b,c的優(yōu)先隊(duì)列了

代碼實(shí)現(xiàn)

type MaxQueue struct {    queue []int    max []int}

func Constructor() MaxQueue {    return MaxQueue{}}

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

func (this *MaxQueue) Push_back(value int)  {    this.queue=append(this.queue,value)    i:=0    for ;i<len(this.max);i++{        if this.max[i]<=value{            break        }    }    this.max=append(this.max[:i],value)}

func (this *MaxQueue) Pop_front() int {    if len(this.queue)==0{        return -1    }    v:=this.queue[0]    this.queue=this.queue[1:]    if v==this.max[0]{        this.max=this.max[1:]    }    return v   }

/** * Your MaxQueue object will be instantiated and called as such: * obj := Constructor(); * param_1 := obj.Max_value(); * obj.Push_back(value); * param_3 := obj.Pop_front(); */

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“golang刷leetcode技巧之如何實(shí)現(xiàn)隊(duì)列的最大值”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來學(xué)習(xí)!