隊(duì)列的最大值

題目來(lái)源：劍指offer59

今天發(fā)一道劍指offer上面的經(jīng)典題目，主要考察面試者的知識(shí)遷移能力，下面我們先來(lái)看一下題目描述。

請(qǐng)定義一個(gè)隊(duì)列并實(shí)現(xiàn)函數(shù) max_value 得到隊(duì)列里的最大值，若隊(duì)列為空，pop_front(出隊(duì)操作) 和 max_value (獲取隊(duì)列最大值)需要返回 -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]

輸入的第一行代表的執(zhí)行函數(shù)，第二行代表的是輸入的值，該題中只有我們的push_back傳入了參數(shù)，輸出代表的為執(zhí)行該函數(shù)時(shí)，函數(shù)的返回值。

個(gè)人認(rèn)為這個(gè)題目還是很不錯(cuò)的，而且也有一定的難度，大家可以試著實(shí)現(xiàn)一下。

為保證嚴(yán)謹(jǐn)性，文章中的所有代碼都經(jīng)過(guò)測(cè)試，大家可以放心食用

暴力解法

暴力法，是因?yàn)槲覀兊膍ax值通過(guò)每次遍歷我們的動(dòng)態(tài)數(shù)組來(lái)獲得。思路很簡(jiǎn)單，我們創(chuàng)建一個(gè)動(dòng)態(tài)數(shù)組，我們每次執(zhí)行max_value函數(shù)時(shí)，通過(guò)遍歷數(shù)組獲得最大值，入隊(duì)操作則用add,出隊(duì)操作則用remove(0)，去除動(dòng)態(tài)數(shù)組的頭元素。

題目代碼：

class?MaxQueue?{
????//動(dòng)態(tài)數(shù)組
????ArrayList?arr?=??new?ArrayList<>();
????public?MaxQueue()?{
???????
????}???????
????public?int?max_value()?{
?????????//為空的情況
?????????if(arr.size()?==?0){
???????????return?-1;
?????????}
?????????//初始化max
?????????int?max?=?Integer.MIN_VALUE;
?????????//遍歷動(dòng)態(tài)數(shù)組，獲取最大值
?????????for(int?i?=?0;i????????????
????????????if(arr.get(i)>max){
???????????????max?=?arr.get(i);
????????????}

?????????}
?????????????return?max;

????}

????public?void?push_back(int?value)?{
????????//添加元素
????????arr.add(value);???

????}

????public?int?pop_front()?{
????????//隊(duì)列為空時(shí)，執(zhí)行該函數(shù)返回-1
???????if(arr.size()?==?0){
???????????return?-1;
???????}else{???
???????????return?arr.remove(0);
???????}
??????
????}
????
}

利用雙端隊(duì)列

deque （double-ended queue，雙端隊(duì)列）是一種具有隊(duì)列和棧的性質(zhì)的數(shù)據(jù)結(jié)構(gòu)。雙端隊(duì)列中的元素可以從兩端彈出，其限定插入和刪除操作在表的兩端進(jìn)行。

我們了解了雙端隊(duì)列之后，是不是感覺(jué)很實(shí)用，很靈活，但實(shí)際上在應(yīng)用程序中遠(yuǎn)不及棧和隊(duì)列有用。我們了解雙端隊(duì)列之后，我們來(lái)聊一下我們的做題思路吧

這個(gè)思路也很簡(jiǎn)單，我們充分利用雙端隊(duì)列的性質(zhì)，因?yàn)樗梢詢(xún)深^出隊(duì)，那我們?cè)陔p端隊(duì)列中僅保存隊(duì)列中每一段的最大值即可，見(jiàn)下圖。

我們分成了三段，第一段的最大值為9，第二段為8，第三段為7。那么我們這個(gè)段是怎么分的呢？

我們看第一段最大值為9前面沒(méi)有其他數(shù)字，第二段最大值為8，前面的三個(gè)數(shù)字都小于8，但是它小于第一段的最大值，同理第三段也是。如果第三段的元素為6，10的話(huà)，那我們的雙端隊(duì)列中只有10啦，因?yàn)樗笥谒暗乃兄怠?/span>

廢話(huà)不多說(shuō)下面我們直接看動(dòng)圖吧。

題目代碼：

class?MaxQueue?{

????Queue?queue?;
????
????Deque?deque;
????public?MaxQueue()?{
????????queue?=?new?LinkedList();
????????
????????deque?=?new?LinkedList();

????}???
????//返回最大值，此時(shí)返回的為depue的第一個(gè)元素
????public?int?max_value()?{
????????if(deque.isEmpty()){
????????????return?-1;
????????}
????????int?max?=?deque.getFirst();
????????return?max;
????}
????
????//入隊(duì)操作
????
????public?void?push_back(int?value)?{
????
????????//普通隊(duì)列直接入隊(duì)
????????
????????queue.offer(value);
????????
????????//雙端隊(duì)列需要先將該階段小于value值的出隊(duì)
????????
????????while(?!deque.isEmpty()?&&?deque.getLast()???????????deque.removeLast();
????????}
????????
????????//入隊(duì)value
????????
????????deque.offer(value);
????????
????}
????
????//出隊(duì)操作，返回兩種情況，隊(duì)頭小于當(dāng)前階段最大值，隊(duì)頭等于當(dāng)前階段最大值
????
????public?int?pop_front()?{
????????if(queue.isEmpty()){
????????????return?-1;
????????}
????????
????????//普通隊(duì)列出隊(duì)
????????
????????int?temp?=?queue.poll();
????????
????????//判斷普通隊(duì)列和雙端隊(duì)列的隊(duì)頭是否相等，兩種返回情況
????????if(temp?==?deque.peekFirst()){
????????????return?deque.pollFirst();
????????}
????????else{
???????????return??temp;
????????}

????}
}