1.括號匹配問題
思路：將左括號壓入棧中，遍歷字符串，當遇到右括號就出棧，判斷是否是匹配的一對，不是就返回false（因為按照順序所以當遇到右括號出棧一定要是匹配的）。使用Map來簡化ifelse?
class Solution {public boolean isValid(String s) {int len = s.length();if(len%2 != 0){return false;}Map<Character,Character> map = new HashMap<>();map.put('(',')');map.put('[',']');map.put('{','}');Deque<Character> stack = new LinkedList<>();for(int i = 0;i<len;i++){char c = s.charAt(i);if(map.containsKey(c)){stack.push(c);}else{if(stack.isEmpty() || c != map.get(stack.pop())){return false;}}}return stack.isEmpty();}
}?2.最小棧
?
關鍵是使用輔助棧，并且同步存取，存的是最新的最小值，如果最小值被彈出棧了，因為同步的原因輔助棧中的最小值也將會消失。
class MinStack {Deque<Integer> min;Deque<Integer> stack;public MinStack() {stack = new LinkedList<>();min = new LinkedList<>();min.push(Integer.MAX_VALUE);}public void push(int val) {stack.push(val);min.push(Math.min(val,min.peek()));}public void pop() {stack.pop();min.pop();}public int top() {return stack.peek();}public int getMin() {return min.peek();}
}3.最大棧
設計一個最大棧數據結構，支持查找最大元素
與最小棧一樣，不同的是需要實現popMax()將棧中最大元素彈出，此處使用額外輔助棧，將原棧中元素彈出放入輔助棧中，待最大的元素找出彈出后，再倒回去。注意的時兩個棧同時存取
class MaxStack {Stack<Integer> stack;Stack<Integer> maxStack;public MaxStack() {stack = new Stack();maxStack = new Stack();}public void push(int x) {int max = maxStack.isEmpty() ? x : maxStack.peek();maxStack.push(max > x ? max : x);stack.push(x);}public int pop() {maxStack.pop();return stack.pop();}public int top() {return stack.peek();}public int peekMax() {return maxStack.peek();}public int popMax() {int max = peekMax();Stack<Integer> buffer = new Stack();while (top() != max) buffer.push(pop());pop();while (!buffer.isEmpty()) push(buffer.pop());return max;}public static void main(String[] args) {MaxStack stack = new MaxStack();stack.push(2);stack.push(5);stack.push(1);System.out.println(stack.top());System.out.println(stack.popMax());System.out.println(stack.peekMax());}
}
)
