(1) 用兩個棧實現(xiàn)隊列

鏈接
很簡單，如果有元素進入隊列，則將其進入stack1。如果要出隊列，那么就需要判斷stack2的情況。人與法國stack2為空，則直接把stack1的元素全放進stack2（相當于順序反過來），然后再出棧。如果不為空，則先出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的操作很簡單，重點是在于min操作。如果直接設(shè)置一個min變量，確實可以記錄最小值。但如果最小值出棧了，那么min就很難再修改。因此只有一個min是無法工作的，需要一個棧來同時記錄，記錄的內(nèi)容為【當前元素入棧時的最小值】
例如，如：-2， 1， 3

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

如果-3入棧：

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

此時就可以得到當前的最小值。如果-3出棧，stack2的也進行pop操作，最小值也能被記錄。時間復(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）有效括號序列

鏈接

即用棧來存儲字符串的內(nèi)容，并且進行判斷。如果匹配則出棧，否則不用出棧，最后判斷棧是否為空。這樣的做法是正確的，不過仍可以優(yōu)化，因為可能出現(xiàn)（] 這樣的情況，其實可以直接退出循環(huá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來存儲映射關(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)建一個HashMap來存儲括號的匹配關(guān)系Map<Character, Character> map = new HashMap<>();map.put(')', '(');map.put(']', '[');map.put('}', '{');// 創(chuàng)建一個棧Stack<Character> stack = new Stack<>();// 遍歷字符串的每個字符for (char ch : s.toCharArray()) {// 如果字符是右括號if (map.containsKey(ch)) {// 彈出棧頂元素，如果棧為空則賦值為一個虛擬字符char topElement = stack.isEmpty() ? '#' : stack.pop();// 檢查棧頂元素是否與當前字符的匹配字符相同if (topElement != map.get(ch)) {return false;}} else {// 如果字符是左括號，壓入棧中stack.push(ch);}}// 如果棧為空，說明所有括號匹配return stack.isEmpty();
}

（4） 滑動窗口的最大值

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

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

1. 初始化雙端隊列為空，結(jié)果列表為空。
2. 遍歷數(shù)組：
   • 第一個元素 2：雙端隊列變?yōu)?[2]。
   • 第二個元素 3：移除 2，雙端隊列變?yōu)?[3]。
   • 第三個元素 4：移除 3，雙端隊列變?yōu)?[4]。窗口達到大小 3，最大值為 4。
   • 第四個元素 2：雙端隊列變?yōu)?[4, 2]。最大值仍為 4。
   • 第五個元素 6：移除 4 和 2，雙端隊列變?yōu)?[6]。最大值為 6。
   • 第六個元素 2：雙端隊列變?yōu)?[6, 2]。最大值仍為 6。
   • 第七個元素 5：移除 2，雙端隊列變?yōu)?[6, 5]。最大值仍為 6。
   • 第八個元素 1：雙端隊列變?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++) {// 移除不在滑動窗口范圍內(nèi)的元素if (i >= size && !deque.isEmpty() && deque.peekFirst() == num[i - size]) {deque.pollFirst();}// 移除所有小于當前元素的元素while (!deque.isEmpty() && deque.peekLast() < num[i]) {deque.pollLast();}// 添加當前元素deque.offerLast(num[i]);// 當窗口大小達到要求時，記錄當前窗口的最大值if (i >= size - 1) {res.add(deque.peekFirst());}}return res;}

（4）最小的K個數(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;}