文章目錄

• 題目描述
• 思路 && 代碼
• • • 二刷

題目描述

恢復(fù)打題的第二天打卡～

• 可以說是這道最小棧的兄弟題目了，很相似
• 總體思路還是一樣，靠空間換時間～
• 也就是借助輔助隊(duì)列
  

思路 && 代碼

• 這篇題解的動圖做得很好，建議結(jié)合食用。
• 核心在于 push() 時的處理：對 maxQueue 的維護(hù)更新
• 關(guān)于時間復(fù)雜度，max、pop 顯而易見是 O(1)。
• 至于 push，有：
  
  也就是實(shí)現(xiàn)了均攤時間復(fù)雜度O(1)

class MaxQueue {// 用輔助隊(duì)列解決，類似最小棧Deque<Integer> queue, max;public static final int emptyNum = -1;public MaxQueue() {queue = new LinkedList<>();max = new LinkedList<>();}public int max_value() {if(max.isEmpty()) {return emptyNum;}// max 隊(duì)列的第一個值就是當(dāng)前的最大值return max.peek();}public void push_back(int value) {queue.addLast(value);// 核心算法：// 1. 等于時也需要存（否則pop會出錯）// 2. 從后往前，把前面的較小值取代（更新維護(hù) max 隊(duì)列）while(!max.isEmpty() && max.getLast() < value) {max.removeLast();}max.addLast(value);}public int pop_front() {if(queue.isEmpty()) {return emptyNum;}int temp = queue.removeFirst();// 如果取出的就是最大值，max就也pop()if(max.peek() == temp) {max.removeFirst();}return temp;} }/*** Your MaxQueue object will be instantiated and called as such:* MaxQueue obj = new MaxQueue();* int param_1 = obj.max_value();* obj.push_back(value);* int param_3 = obj.pop_front();*/

二刷

• 核心思路還是同上，就是注意隊(duì)列中對比不能用 ==

class MaxQueue { Deque<Integer> queue = new ArrayDeque<>();Deque<Integer> maxQueue = new ArrayDeque<>();public MaxQueue() {}public int max_value() {if(queue.isEmpty()) {return -1;}return maxQueue.element();}public void push_back(int value) {queue.offer(value);while(!maxQueue.isEmpty() && maxQueue.getLast() < value) {maxQueue.pollLast();}maxQueue.offer(value);}public int pop_front() {if(queue.isEmpty()) {return -1;}if(queue.element().equals(maxQueue.element())) {maxQueue.poll();}return queue.poll();} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode笔记】剑指 Offer 59 - II. 队列的最大值（Java、辅助队列）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。