(1) 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列

鏈接
很簡(jiǎn)單，如果有元素進(jìn)入隊(duì)列，則將其進(jìn)入stack1。如果要出隊(duì)列，那么就需要判斷stack2的情況。人與法國(guó)stack2為空，則直接把stack1的元素全放進(jìn)stack2（相當(dāng)于順序反過來），然后再出棧。如果不為空，則先出stack2的內(nèi)容。

import java.util.*;
import java.util.Stack;public class Solution {Stack<Integer> stack1 = new Stack<Integer>();Stack<Integer> stack2 = new Stack<Integer>();public void push(int node) {stack1.add(node);}public int pop() {if(stack2.isEmpty()){while(!stack1.isEmpty()){stack2.add(stack1.pop());}}return stack2.pop();}
}

（2）包含min函數(shù)的棧

鏈接

pop和push的操作很簡(jiǎn)單，重點(diǎn)是在于min操作。如果直接設(shè)置一個(gè)min變量，確實(shí)可以記錄最小值。但如果最小值出棧了，那么min就很難再修改。因此只有一個(gè)min是無法工作的，需要一個(gè)棧來同時(shí)記錄，記錄的內(nèi)容為【當(dāng)前元素入棧時(shí)的最小值】
例如，如：-2， 1， 3

stack1：-2 1 3
stack2：-2 -2 -2

如果-3入棧：

stack1：-2 1 3 -3
stack2：-2 -2 -2 -3

此時(shí)就可以得到當(dāng)前的最小值。如果-3出棧，stack2的也進(jìn)行pop操作，最小值也能被記錄。時(shí)間復(fù)雜度是O(1)。

import java.util.*;
import java.util.Stack;public class Solution {Stack<Integer> s1=new Stack<>();Stack<Integer> s2=new Stack<>();int min=10001;public void push(int node) {s1.add(node);if(node<min){s2.add(node);min=node;}else{s2.add(min);}}public void pop() {s1.pop();s2.pop();min=s2.peek();}public int top() {return s1.peek();}public int min() {return s2.peek();}
}

（3）有效括號(hào)序列

鏈接

即用棧來存儲(chǔ)字符串的內(nèi)容，并且進(jìn)行判斷。如果匹配則出棧，否則不用出棧，最后判斷棧是否為空。這樣的做法是正確的，不過仍可以優(yōu)化，因?yàn)榭赡艹霈F(xiàn)（] 這樣的情況，其實(shí)可以直接退出循環(huán)。不過這樣寫很簡(jiǎn)潔。

public boolean isValid (String s) {// write code hereStack<Character> stack=new Stack<>();for(char ch: s.toCharArray()){if(stack.isEmpty()){stack.push(ch);}else{if(ch==')'&&stack.peek()=='(' || ch==']'&&stack.peek()=='[' ||ch=='}'&&stack.peek()=='{'){stack.pop();}else{stack.push(ch);}}}return stack.isEmpty();}

我們可以優(yōu)化一下，寫得更復(fù)雜，或者用hash來存儲(chǔ)映射關(guān)系。

public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (char ch : s.toCharArray()) {if (ch == '(' || ch == '[' || ch == '{') {stack.push(ch);} else if (ch == ')' && !stack.isEmpty() && stack.peek() == '(') {stack.pop();} else if (ch == ']' && !stack.isEmpty() && stack.peek() == '[') {stack.pop();} else if (ch == '}' && !stack.isEmpty() && stack.peek() == '{') {stack.pop();} else {return false;}}return stack.isEmpty();
}
// 或者這樣
public boolean isValid(String s) {// 創(chuàng)建一個(gè)HashMap來存儲(chǔ)括號(hào)的匹配關(guān)系Map<Character, Character> map = new HashMap<>();map.put(')', '(');map.put(']', '[');map.put('}', '{');// 創(chuàng)建一個(gè)棧Stack<Character> stack = new Stack<>();// 遍歷字符串的每個(gè)字符for (char ch : s.toCharArray()) {// 如果字符是右括號(hào)if (map.containsKey(ch)) {// 彈出棧頂元素，如果棧為空則賦值為一個(gè)虛擬字符char topElement = stack.isEmpty() ? '#' : stack.pop();// 檢查棧頂元素是否與當(dāng)前字符的匹配字符相同if (topElement != map.get(ch)) {return false;}} else {// 如果字符是左括號(hào)，壓入棧中stack.push(ch);}}// 如果棧為空，說明所有括號(hào)匹配return stack.isEmpty();
}

（4） 滑動(dòng)窗口的最大值

鏈接
這題的做法其實(shí)比較固定，如果不暴力做就需要使用雙端隊(duì)列。
我們的隊(duì)列元素大小總是非遞增的，這樣就可以很輕松的獲取最大值。同時(shí)還要注意窗口內(nèi)的元素達(dá)到3的情況。

假設(shè)數(shù)組是 [2, 3, 4, 2, 6, 2, 5, 1]，窗口大小是 3。

1. 初始化雙端隊(duì)列為空，結(jié)果列表為空。
2. 遍歷數(shù)組：
   • 第一個(gè)元素 2：雙端隊(duì)列變?yōu)?[2]。
   • 第二個(gè)元素 3：移除 2，雙端隊(duì)列變?yōu)?[3]。
   • 第三個(gè)元素 4：移除 3，雙端隊(duì)列變?yōu)?[4]。窗口達(dá)到大小 3，最大值為 4。
   • 第四個(gè)元素 2：雙端隊(duì)列變?yōu)?[4, 2]。最大值仍為 4。
   • 第五個(gè)元素 6：移除 4 和 2，雙端隊(duì)列變?yōu)?[6]。最大值為 6。
   • 第六個(gè)元素 2：雙端隊(duì)列變?yōu)?[6, 2]。最大值仍為 6。
   • 第七個(gè)元素 5：移除 2，雙端隊(duì)列變?yōu)?[6, 5]。最大值仍為 6。
   • 第八個(gè)元素 1：雙端隊(duì)列變?yōu)?[6, 5, 1]。最大值為 6。

最終結(jié)果列表為 [4, 4, 6, 6, 6, 5]。

 public ArrayList<Integer> maxInWindows(int[] num, int size) {ArrayList<Integer> res = new ArrayList<>();if (num == null || size <= 0 || num.length < size) {return res;}Deque<Integer> deque = new LinkedList<>();for (int i = 0; i < num.length; i++) {// 移除不在滑動(dòng)窗口范圍內(nèi)的元素if (i >= size && !deque.isEmpty() && deque.peekFirst() == num[i - size]) {deque.pollFirst();}// 移除所有小于當(dāng)前元素的元素while (!deque.isEmpty() && deque.peekLast() < num[i]) {deque.pollLast();}// 添加當(dāng)前元素deque.offerLast(num[i]);// 當(dāng)窗口大小達(dá)到要求時(shí)，記錄當(dāng)前窗口的最大值if (i >= size - 1) {res.add(deque.peekFirst());}}return res;}

（4）最小的K個(gè)數(shù)

鏈接
最好想的就是直接排序再切片。

public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {// write code hereArrays.sort(input);ArrayList<Integer> result = new ArrayList<>();for (int i = 0; i < k; i++) {result.add(input[i]);}return result;}