溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了golang刷leetcode技巧之如何實現隊列的最大值，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。
請定義一個隊列并實現函數 max_value 得到隊列里的最大值，要求函數max_value、push_back 和 pop_front 的時間復雜度都是O(1)。
若隊列為空，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的總操作數 <= 10000
1 <= value <= 10^5
解題思路：
1，對于先進先出，O（1）,顯然是一個基本的隊列可以搞定
2，但是實現O（1）的max，需要優先隊列
3，但是本題的技巧在于:優先隊列只需要按照插入順序，保留前幾個
4，具體原因：
A，如果插入元素比現在優先隊列元素都小，插入隊尾即可，這很好理解
B，如果插入元素A比現在優先隊列某些元素a,b,c大，那么，a,b,c 出隊的時候,最大元素肯定大于等于A，所以，沒有必要維護a,b,c的優先隊列了
代碼實現
type MaxQueue struct {queue []intmax []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:=0for ;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();*/
感謝你能夠認真閱讀完這篇文章，希望小編分享的“golang刷leetcode技巧之如何實現隊列的最大值”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
