目錄
單調隊列單調棧
隊列和雙端隊列基礎
劍指offer59②隊列的最大值
劍指 Offer 59 - I. 滑動視窗的最大值
棧 基礎
最小棧
42.接雨水 難度 困難
739.每日溫度 難度 中等
隊列和棧
劍指Offer09用兩個棧實作隊列
單調隊列單調棧
隊列和雙端隊列基礎
Queue中offer()入隊，poll()出隊，peek()查詢頭部元素。offer，add差別，poll，remove差別，peek，element差別,前面對空操作不會抛出異常。
deque是雙端隊列。
Deque<Integer> deque = new LinkedList<>();
deq.peekLast()傳回此雙端隊清單示的最後一個元素，否則當此雙端隊列為“空白”時傳回null。deq.peekfirst()檢索連結清單的第一個元素，初始元素或開始元素，但不會從清單中删除第一個元素。
deq.offerLast(value)指定元素添加在清單的末尾，pollLast()傳回清單的最後一個元素并從清單中移除。
pollFirst()檢索并移除此清單的第一個元素，或者如果此清單為空，則傳回null。
單調棧含義就是棧内的元素是單調的，我們這兩個題目用到的都是遞減棧（相同也可以），我們依次将元素壓入棧，如果目前元素小于等于棧頂元素則入棧，如果大于棧頂元素則先将棧頂不斷出棧，直到目前元素小于或等于棧頂元素為止，然後再将目前元素入棧。
劍指offer59②隊列的最大值
使用輔助雙端隊列deq
入隊操作解釋：入隊queue直接入隊，dequeue先比較最後一個元素，比要入隊元素小的先出隊（從後面），然後再入隊deq.offerLast(value);
傳回隊頭元素解釋：如果que為空傳回-1，不為空 如果que和deq的第一個元素相等（取第一個元素寫法不同，比較用equal que.peek().equals(deq.peekFirst()) ）
我們之前說過的隊列，遵守先進先出的規則，雙端隊列則可以從隊頭出隊，也可以從隊尾出隊。隊尾入隊。
我們可以用雙端隊列做輔助隊列，用輔助隊列來儲存目前隊列的最大值。我們同時定義一個普通隊列和一個雙端單調隊列。普通隊列就正常執行入隊，出隊操作。max_value 操作則傳回咱們的雙端隊列的隊頭即可。
class MaxQueue {
//普通隊列
Queue<Integer> que;
//雙端隊列
Deque<Integer> deq;
public MaxQueue() {
que = new LinkedList<>();
deq = new LinkedList<>();
}
//擷取最大值值，傳回我們雙端隊列的對頭即可，因為我們雙端隊列是單調遞減的嘛
public int max_value() {
return deq.isEmpty() ? -1 : deq.peekFirst();
}
//入隊操作
public void push_back(int value) {
que.offer(value);
//維護單調遞減
while (!deq.isEmpty() && value > deq.peekLast()){
deq. pollLast();
}
deq.offerLast(value);
}
//傳回隊頭元素，此時有個細節，我們需要用equals
//這裡需要使用 equals() 代替 == 因為隊列中存儲的是 int 的包裝類 Integer
public int pop_front() {
if(que.isEmpty()) return -1;
if (que.peek().equals(deq.peekFirst())) {
deq.pollFirst();
}
return que.poll();
}
}
public int pop_front() {
if(que.isEmpty()) return -1; //que為空
if (que.peek().equals(deq.peekFirst())) { //比較如果第一個元素相同
deq.pollFirst(); //deq第一個元素出隊
}
return que.poll(); //que第一個元素出隊
劍指 Offer 59 - I. 滑動視窗的最大值
給定一個數組
nums
和滑動視窗的大小
k
，請找出所有滑動視窗裡的最大值。
示例:
輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7]
解釋:
滑動視窗的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
來源：力扣（LeetCode）
和上一題類似
1.想将我們第一個視窗的所有值存入單調雙端隊列中，單調隊列裡面的值為單調遞減的。如果發現隊尾元素小于要加入的元素，則将隊尾元素出隊，直到隊尾元素大于新元素時，再讓新元素入隊，目的就是維護一個單調遞減的隊列。
2.我們将第一個視窗的所有值，按照單調隊列的規則入隊之後，因為隊列為單調遞減，是以隊頭元素必為目前視窗的最大值，則将隊頭元素添加到數組中。
3.移動視窗，判斷目前視窗前的元素是否和隊頭元素相等，如果相等則出隊。
4.繼續然後按照規則進行入隊，維護單調遞減隊列。
5.每次将隊頭元素存到傳回數組裡。
5.傳回數組
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
if (len == 0) {
return nums;
}
int[] arr = new int[len - k + 1];
int arr_index = 0;
//我們需要維護一個單調遞增的雙向隊列
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < k; i++) {
while (!deque.isEmpty() && deque.peekLast() < nums[i]) {
deque.removeLast(); //隊頭保留最大的 為什麼用remove不用poll？
}
deque.offerLast(nums[i]); //值小的出隊完，入隊
}
arr[arr_index++] = deque.peekFirst(); //數組賦第一個值
for (int j = k; j < len; j++) { //j指針從k位置開始周遊到最後 滑動視窗
if (nums[j - k] == deque.peekFirst()) { //j-k是目前視窗的第一個的前一個
deque.removeFirst(); //最大值是前一個視窗的，删除
}
while (!deque.isEmpty() && deque.peekLast() < nums[j]) { //nums[j]要進，隊現有的後面的比它小的都出隊 （固定寫法）
deque.removeLast();
}
deque.offerLast(nums[j]); //進隊
arr[arr_index++] = deque.peekFirst(); //數組賦剩餘的值，
}
return arr;
}
}
為什麼要比較相同？後來補充：因為不能把即将周遊的視窗中的最大值删掉，隻有最大值是前一個視窗的才删
if (nums[j - k] == deque.peekFirst()) {
deque.removeFirst();
}
棧 基礎
Stack<Integer> A,B; 定義棧
public MinStack() {
A = new Stack<>();
B = new Stack<>();
}
B.isEmpty()//判斷空 B.peek()//棧頂值 不删除
B.push(x)//入棧 A.peek()//出線
最小棧
設計一個支援 push ，pop ，top 操作，并能在常數時間内檢索到最小元素的棧。
- push(x) —— 将元素 x 推入棧中。
- pop() —— 删除棧頂的元素。
- top() —— 擷取棧頂元素。
- getMin() —— 檢索棧中的最小元素。
輸入：
["MinStack","push","push","push","getMin","pop","top","getMin"] > [[],[-2],[0],[-3],[],[],[],[]]
輸出：
[null,null,null,null,-3,null,0,-2]
和隊列的最大值類似，使用輔助棧
1.我們執行入棧操作時，先觀察需要入棧的元素是否小于棧 B 的棧頂元素，如果小于則兩個棧都執行入棧操作。
2.棧 B 的棧頂元素則是棧 A 此時的最小值。則 getMin() 隻需傳回棧 B 的棧頂元素即可。
3.出棧時，需要進行對比，若棧 A 和棧 B 棧頂元素相同，則同時出棧，出棧好 B 的棧頂儲存的仍為此時棧 A 的最小元素
class MinStack {
//初始化
Stack<Integer> A,B;
public MinStack() {
A = new Stack<>();
B = new Stack<>();
}
//入棧，如果插入值，目前插入值小于棧頂元素，則入棧，棧頂元素儲存的則為目前棧的最小元素
public void push(int x) {
A.push(x);
if (B.isEmpty() || B.peek() >= x) { //B空也push
B.push(x); //要存最小，是以＞＝
}
}
//出棧，如果A出棧等于B棧頂元素，則說明此時棧内的最小元素改變了。
//這裡需要使用 equals() 代替 == 因為 Stack 中存儲的是 int 的包裝類 Integer
public void pop() {
if (A.pop().equals(B.peek()) ) { //pop删除（和remove對應） peek傳回元素（和element對應）
B.pop();
}
}
//A棧的棧頂元素
public int top() {
return A.peek();
}
//B棧的棧頂元素
public int getMin() {
return B.peek();
}
}
//入棧，如果插入值，目前插入值小于棧頂元素，則入棧，棧頂元素儲存的則為目前棧的最小元素
public void push(int x) {
A.push(x);
if (B.isEmpty() || B.peek() >= x) {
B.push(x);
}
}
//出棧，如果A出棧等于B棧頂元素，則說明此時棧内的最小元素改變了。
//這裡需要使用 equals() 代替 == 因為 Stack 中存儲的是 int 的包裝類 Integer
public void pop() {
if (A.pop().equals(B.peek()) ) {
B.pop();
}
}
但是沒有比較之後棧頂元素出棧的操作，為什麼隊列有？後來補充：沒想通
42.接雨水 難度 困難
單調 遞減棧，從最低到最高，按層算
隻懂思路
739.每日溫度 難度 中等
上題的簡化版。T是給定的溫度數組，自己定義stack通過下标的運算計算出天數，T和stack通過下标聯系起來。
初始i=0，不會運作while，直接push（i） 學習這個寫法
for (int i = 0; i < len; i++) {
//單調棧
while (!stack.isEmpty() && T[i] > T[stack.peek()]){
arr[stack.peek()] = i - stack.pop();
}
stack.push(i);
}
隊列和棧
劍指Offer09用兩個棧實作隊列
class CQueue {
//初始化兩個棧
Stack<Integer> stack1,stack2;
public CQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
//入隊，我們往第一個棧壓入值
public void appendTail (int value) {
stack1.push(value);
}
//出隊
public int deleteHead() {
//大家可以自己思考一下為什麼if條件為stack2.isEmpty(),細節所在
if (stack2.isEmpty()) {
//如果此時A棧沒有值，則直接-1，我們可以看示例
if (stack1.isEmpty()) {
return -1;
}
//将A棧的值，壓入B棧中
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
核心的出隊代碼
//出隊
public int deleteHead() {
//大家可以自己思考一下為什麼if條件為stack2.isEmpty(),細節所在
//思考這不很簡單嗎
if (stack2.isEmpty()) {
//如果此時A棧沒有值，則直接-1，我們可以看示例
if (stack1.isEmpty()) {
return -1;
}
//将A棧的值，壓入B棧中
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
鼓感覺還行 18:02