棧和隊列

stack Class

google stack java 8/12

empty()
peek()
pop()
push(E item)
search(Object o)

最近相關性會用到棧

queue Interface

• Throws exception:
  add(e)
  remove()
  element()
• Returns special value:
  offer()
  peek()
  poll()

大多滑動窗口的題目，用隊列解決即可。

Deque Interface

ArrayDeque,LinkedList…

API與queue類似，乘二。
分為First和Last。

add 和 push

當我們使用Deque實現棧的功能時，注意要用push（==addFirst）。不要寫成add（==addLast）

LinkedList實現的Deque，peek，pop，push都是在列表頭進行操作。

Priority Queue – Class

1. 插入O(1)
2. 取出O(lonN)- 按照元素的優先性
3. 底層具體實現多樣，可以用heap堆、bst、treap

題目

1. 有效的括號

class Solution {public boolean isValid(String s) {Deque < Character > deque = new LinkedList<>();//注意實例化的寫法//用了char，后續都要用單引號，不能用雙引號Stringchar ch ;for ( int i = 0 ; i < s.length() ; i++ ){ch = s.charAt(i);//charAt的寫法if( ch == '('){deque.push(')');//這里deque是push，不是append。更不是add。}else if(ch == '['){deque.push(']');}else if(ch =='{' ){deque.push('}');}//下面一行搞錯了，如果過程中deque就空了，也要返回false。所以不能是且，是或//else if(deque.isEmpty()!=false && ch != deque.peek()){else if(deque.isEmpty() || ch != deque.peek()){return false;}else{deque.pop();}}return deque.isEmpty();}
}

2. 最小棧

設計一個支持 push ，pop ，top 操作，并能在常數時間內檢索到最小元素的棧。

實現 MinStack 類:

MinStack() 初始化堆棧對象。
void push(int val) 將元素val推入堆棧。
void pop() 刪除堆棧頂部的元素。
int top() 獲取堆棧頂部的元素。
int getMin() 獲取堆棧中的最小元素。

class MinStack {// 兩個棧即可實現private Stack<Integer> stack;private Stack<Integer> min_stack;public MinStack() {stack = new Stack<>();min_stack = new Stack<>();}public void push(int val) {stack.push(val);if(min_stack.isEmpty() || val<=min_stack.peek() )min_stack.push(val);}public void pop() {if(stack.pop().equals(min_stack.peek()))min_stack.pop();}public int top() {return stack.peek();}public int getMin() {return min_stack.peek();}
}

3. 柱狀圖中的最大矩形面積

給定非負整數數組 heights ，數組中的數字用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。

求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。

class Solution {public int largestRectangleArea(int[] heights) {//暴力：遍歷每一個，左右到比他更小就停，總結矩形面積。On方//單調棧Stack<Integer> stack = new Stack<>();stack.push(-1);int maxArea = 0;for(int i = 0 ; i <heights.length ; i ++){//每次有新元素就和棧頂比較大小，直到入棧。//棧頂大則pop，且計算pop的index對應的area//棧頂小則入棧，不用計算areawhile(stack.peek() != -1 && heights[stack.peek()] > heights[i]){int index = stack.pop() ;maxArea = Math.max( maxArea , heights[index] * (i-stack.peek()-1));}//千萬別忘了入棧stack.push(i);}while(stack.peek() != -1){int index = stack.pop() ;//錯誤寫法，計算錯誤//maxArea = Math.max( maxArea , heights[index] * (index-stack.peek()-1));maxArea = Math.max( maxArea , heights[index] * (heights.length-stack.peek()-1));}return maxArea;}
}

優化方法： 單調棧
每一個點要有左右邊界。
為了找邊界，可以用棧。

維護一個棧，棧里元素從小到大排列。
（實際上可以是棧里放index，隨時可以查到對應的height，height才是從小到大排列）

向右走一位，進行至少一次判斷。

發現新高度小于棧頂，則說明有一個右邊界可以確定。

而左邊界一直是棧里該元素的下面一位（下一位是他左邊剛好比他小的那一個）的下標。

Area=(right- left -1)*index;

pop之后繼續判斷，若新高度小于棧頂，重復上述過程。直到新高度大于棧頂高度，新高度入棧。

棧底用 -1
則left = （-1）時公式不變，邊界處理一致。

class Solution {public int largestRectangleArea(int[] heights) {//暴力：遍歷每一個，左右到比他更小就停，總結矩形面積。On方//單調棧Stack<Integer> stack = new Stack<>();stack.push(-1);int maxArea = 0;for(int i = 0 ; i <heights.length ; i ++){//每次有新元素就和棧頂比較大小，直到入棧。//棧頂大則pop，且計算pop的index對應的area//棧頂小則入棧，不用計算areawhile(stack.peek() != -1 && heights[stack.peek()] > heights[i]){maxArea = Math.max( maxArea , heights[stack.pop()] * (i-stack.peek()-1));}//千萬別忘了入棧stack.push(i);}while(stack.peek() != -1){//錯誤寫法，計算錯誤//maxArea = Math.max( maxArea , heights[index] * (index-stack.peek()-1));maxArea = Math.max( maxArea , heights[stack.pop()] * (heights.length-stack.peek()-1));}return maxArea;}
}

codestyle

每一個括號和運算符前后都應該加空格。

IDEA 操作

快捷鍵

Home End鍵——行頭行尾
刪除行 ctrl + Y

選擇

擴選 ctrl + W
縮選 ctrl + Shift + W

代碼生成類

Alt+Insert：在目錄中使用該快捷鍵可以新建包，文件，類。在 java 文件中可以進行 setter，getter，構造方法，toString等方法生成，生成方法覆蓋（重寫）。
Ctrl+Shift+空格：智能代碼提示，代碼自動補全。可用于強制類型轉換補全，new 對象補全，return 補全等。
Ctrl+Shift+Enter：自動補全代碼結構。自動生成 if, do-while, try-catch, return（或方法調用） 語法正確的代碼結構，比如添加括號和大括號。