隊(duì)列:先進(jìn)先出
棧:先進(jìn)后出
堆(優(yōu)先隊(duì)列 ): 邏輯結(jié)構(gòu)上是完全二叉樹(shù)結(jié)構(gòu)婆跑，其中每個(gè)字?jǐn)?shù)的最大值(最小值)節(jié)點(diǎn)是頭節(jié)點(diǎn)。實(shí)際結(jié)構(gòu)常用數(shù)組實(shí)現(xiàn)庭呜。 建立一個(gè)大根堆 時(shí)間復(fù)雜度O(n)
基礎(chǔ)題
1.數(shù)組實(shí)現(xiàn)棧滑进、隊(duì)列 ； 實(shí)現(xiàn)堆排序
- 棧
class ArrayStack{
int maxSize;
int top;
int []stack;
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
top=-1;
stack=new int[maxSize];
}
//椖蓟眩空
public boolean isEmpty(){
return top==-1;
}
//棧滿
public boolean isFull(){
return top==maxSize-1;
}
//入棧
public void push(int i){
if(isFull()) {
System.out.println("棧已滿");
return;
}
stack[++top]=i;
}
//出棧
public int pop(){
if(isEmpty()){
throw new RuntimeException("椃龉兀空");
}
int val=stack[top];
top--;
return val;
}
//顯示棧頂元素，不出棧
public int showPop(){
if(isEmpty()){
throw new RuntimeException("椊矗空");
}
return stack[top];
}
//遍歷
public void show(){
if(isEmpty()){
System.out.println("椡陨螅空");
return;
}
for (int i = 0; i <=top; i++) {
System.out.printf("stack[%d]=%d \n",i,stack[i]);
}
}
- 隊(duì)列
class ArrayCircleQueue {
private int maxSize;
private int front; //指向隊(duì)頭
private int rear; //指向隊(duì)尾的后一個(gè)位置,且rear后預(yù)留一個(gè)位置，方便判斷隊(duì)空
private int []circleArr;
public ArrayCircleQueue(int maxSize) {
this.maxSize = maxSize; //因?yàn)轭A(yù)留一個(gè)位置吉执，實(shí)際上只有maxSize-1個(gè)數(shù)有效
front=0;
rear=0;
circleArr=new int[maxSize];
}
public int getMaxSize() {
return maxSize;
}
public int getFront() {
return front;
}
public int getRear() {
return rear;
}
//判斷隊(duì)空
public boolean isEmpty(){
return rear==front;
}
//判斷隊(duì)滿
public boolean isFull(){
return (rear+1)%maxSize==front;
}
//入隊(duì)
public void enqueue(int i){
if(isFull()){
System.out.println("隊(duì)列已滿疯淫，不能添加數(shù)據(jù)");
return;
}
circleArr[rear]=i;
rear=(rear+1)%maxSize;
}
//出隊(duì)
public int dequeue(){
if(isEmpty()){
return -1;
}
int temp=front;
front=(front+1)%maxSize;
return circleArr[temp];
}
}
- 堆
//給定數(shù)組 建立大根堆
public static void main(String[] args){
int[] a={.......};
int len=a.length;
//建立大根堆
for(int i=len/2-1 ; i>=0; i--){
heapSort(a,i,len);
}
for(int i=len-1;i>0;i--){
int temp=a[i];
a[i]=a[0];
a[0]=a[i];
heapSort(a,0,i);
}
}
public int[] heapSort(int[] a,int i, int len){
int temp=a[i];
for(int j=2*i+1 ; j<len;j=2*j+1){
if(j+1<len && a[j]<a[j+1]) j++;
if(a[j]>temp){
a[i]=a[j];
i=j;
}else break;
}
a[i]=temp;
}
2.用棧實(shí)現(xiàn)隊(duì)列 ； 用隊(duì)列實(shí)現(xiàn)棧
//棧實(shí)現(xiàn)隊(duì)列
class MyQueue {
Stack<Integer> res = new Stack<>();
public MyQueue() {}
public void push(int x) {
Stack<Integer> temp = new Stack<>();
while(!res.isEmpty()) temp.push(res.pop());
temp.push(x);
while(!temp.isEmpty()) res.push(temp.pop());
}
public int pop() {
return res.pop();
}
public int peek() {
return res.peek();
}
public boolean empty() {
return res.isEmpty();
}
//隊(duì)列實(shí)現(xiàn)棧
同樣準(zhǔn)備兩個(gè)隊(duì)列
class MyStack {
Queue<Integer> res = new LinkedList<>();
}
public void push(int x) {
Queue<Integer> temp=new LinkedList<>();
temp.add(x);
while(res.peek()!=null) temp.add(res.poll());
while(temp.peek()!=null) res.add(temp.poll());
}
public int pop() {
return res.poll();
}
public int top() {
return res.peek();
}
public boolean empty() {
return res.peek()==null;
}
}
3.實(shí)現(xiàn)一個(gè)特殊的棧戳玫，在實(shí)現(xiàn)棧的基本功能的基礎(chǔ)上,再實(shí)現(xiàn)返回棧中最小元素的操作
//另外定義一個(gè)最小棧 min_stack
class GetMinStack{
public GetMinStack{
}
public void push(int x){
if(min_stack.isEmpty() || x<min_stack.peek() ){
min_stack.push(x);
}else min_stack.push(min_stack.peek());
stack.push(x);
}
public int pop(){
min_stack.pop();
return stack.pop();
}
public int getMin(){
return min_stack.peek();
}
}
4.驗(yàn)證棧序列
輸入兩個(gè)整數(shù)序列熙掺，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷第二個(gè)序列是否為該棧的彈出順序咕宿。假設(shè)壓入棧的所有數(shù)字均不相等币绩。例如蜡秽，序列 {1,2,3,4,5} 是某棧的壓棧序列，序列 {4,5,3,2,1} 是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列缆镣，但 {4,3,5,1,2} 就不可能是該壓棧序列的彈出序列芽突。 ==棧中元素不重復(fù)==
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>();
int r = 0;
for(int i = 0 ; i < pushed.length ; i++){
stack.push(pushed[i]);
while(!stack.isEmpty() && stack.peek() == popped[r]){
stack.pop();
r++;
}
}
return stack.isEmpty();
}
5.有一個(gè)整數(shù)數(shù)組，找出數(shù)組中第K大的數(shù)董瞻。
要找第K大的數(shù)寞蚌，需要維持一個(gè)大小為K的小根堆 ， 遍歷結(jié)束結(jié)果就是小根堆的堆頂钠糊。
對(duì)于為什么是小根堆 挟秤，如果遍歷的數(shù)比堆頂小 ，那肯定其他數(shù)都小 抄伍，如果比堆頂大艘刚，就替換堆頂，重新維持小根堆
public class Finder {
public int findKth(int[] a, int n, int K) {
// write code here
int[] heap = new int[K];
for(int i = 0 ; i < K ; i++) heap[i] = a[i];
for(int i = K/2 - 1 ; i >= 0 ; i--) heapSort(heap,i);
for(int i = K ; i < a.length ; i++){
if(a[i] > heap[0]) heap[0] = a[i];
heapSort(heap,0);
}
return heap[0];
}
public void heapSort(int[] heap , int i){
int temp = heap[i];
for(int j = 2*i + 1 ; j < heap.length ; j = 2*j + 1){
if(j+1 < heap.length && heap[j] > heap[j+1]) j++;
if(heap[j] < temp){
heap[i] = heap[j];
i = j;
}else break;
}
heap[i] = temp;
}
}
進(jìn)階
1.一個(gè)棧一次壓入1,2,3,4,5截珍， 將這個(gè)棧中元素逆序攀甚，即輸出1、2笛臣、3云稚、4、5沈堡，僅用遞歸實(shí)現(xiàn)静陈，不用其他數(shù)據(jù)結(jié)構(gòu)
! 遞歸的本質(zhì)就是棧
public int getStackBottom(Stack<Integer> stack){
int res=stack.pop();
if(stack.isEmpty()) return res;
int last=getStackBottom(stack);
stack.push(res);
return last;
}
public void reverse(Stack<Integer> stack){
if(stack.isEmpty()) return;
int bot=getStackBottom(stack);
reverse(stack);
stack.push(bot);
}
2.更新滑動(dòng)窗口 最大值 最小值問(wèn)題
! 雙端隊(duì)列 隊(duì)列存放數(shù)組元素的下標(biāo)
以更新最大值為例
1.對(duì)于從右側(cè)窗口新進(jìn)入的數(shù)a ，不斷從雙端隊(duì)列的隊(duì)尾釋放小于等于 a 的數(shù)诞丽，直到遇到一個(gè)大于a的數(shù)或者隊(duì)列為空時(shí) 鲸拥， 把 a 從雙端隊(duì)列的隊(duì)尾放入
2.對(duì)于左側(cè)窗口的數(shù)字b ，判斷下標(biāo)是否屬于滑動(dòng)窗口內(nèi) 僧免， 如果不是則彈出
3.這樣就保證隊(duì)頭是該滑動(dòng)窗口的最大值
給定一個(gè)數(shù)組nums ,有一個(gè)大小為k的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)刑赶。返回滑動(dòng)窗口最大值
public int[] maxSlidingWindow(int[] nums, int k) {
LinkedList<Integer> list = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
int j = 0;
for(int i = 0 ; i < nums.length ; i++){
while(!list.isEmpty() && nums[list.getLast()] < nums[i]){
list.removeLast();
}
list.addLast(i);
if(list.getFirst() == i-k) list.removeFirst();
if(i >= k-1) res[j++] = nums[list.getFirst()];
}
return res;
}
3.單調(diào)棧
單調(diào)棧可以用來(lái)找 一個(gè)數(shù)組中 左邊離他最近比他大(小)的數(shù) 和 右邊離他最近比他大(小)的數(shù)
如果找 大數(shù) 就是單調(diào)遞減棧 遍歷數(shù)組 遇到比棧頂小的元素 直接入棧懂衩， 遇到比棧頂大的元素撞叨，棧頂出棧
新棧頂就是左邊離他最近比他大的數(shù) ，要 push的數(shù)就是右邊離他最近比他大的數(shù)
3.a給定 n 個(gè)非負(fù)整數(shù)浊洞，用來(lái)表示柱狀圖中各個(gè)柱子的高度牵敷。每個(gè)柱子彼此相鄰，且寬度為 1 法希。求在該柱狀圖中枷餐，能夠勾勒出來(lái)的矩形的最大面積
LeetCode84.png
// 對(duì)于每個(gè)柱子 往兩邊擴(kuò)散 直到遇到比它小的柱子 就求出以這個(gè)柱子為中心的矩形面積
// 以某個(gè)柱子 i 為中心 ，也就是生成的矩形高為 heights[i]
// 利用單調(diào)遞增棧 求出 每個(gè)柱子 左邊最近比它小的柱子 和 右邊 最近比它小的柱子
// 每次某個(gè)元素出棧的時(shí)候 苫亦，要入棧的元素就是它右邊最近比它小的元素 毛肋， 出棧后的棧頂(新元素還沒(méi)入棧)就是它左邊最近比它小的元素 怨咪，如果出棧后棧為空， 那么就是說(shuō)這個(gè)元素左邊沒(méi)有比它小的元素润匙，可以定義左邊比它小的元素下標(biāo)為-1
// 對(duì)于 相等的元素诗眨，一樣進(jìn)行出棧 ，因?yàn)榧词骨耙粋€(gè)相等的元素提前出棧趁桃，以它為中心生成的最大矩形 一定 被后一個(gè)相等元素生成的矩形囊括
public int getMaxRect(int[] heights){
Stack<Integer> stack = new Stack<Integer> stack; //棧中存放的是柱子的下標(biāo)
int maxSize=0;
for(int i=0;i<heights.length;i++){
while(!stack.isEmpty() && heights[i] <= height[stack.peek()]){
int j = stack.pop() //記錄中心柱子辽话，即矩形的高
int l = stack.isEmpty()? -1 : stack.peek();
int curSize=heights[j] * (i-l-1);
maxSize = Math.max(maxSize,curSize);
}
stack.push(i);
}
//如果棧中還有元素 那么棧中元素的右邊沒(méi)有比它小的數(shù) 即右邊下標(biāo)為heights.length
while(!stack.isEmpty){
int i=stack.pop();
int l= stack.isEmpty()? -1 : stack.peek();
int curSize = heights[i] * (heights.length-l-1);
maxSize = Math.max(maxSize,curSize);
}
return maxSize;
}
3.b 進(jìn)階 最大矩形
LeetCode85.png
思路
- 遍歷每一行， 以每一行中的幾個(gè)元素為底 卫病， 求出每一行的最大矩形
- 對(duì)于每一行，都可以看成一個(gè)柱狀圖典徘，如上圖中的第三行 對(duì)應(yīng)的柱狀圖 就是 [3,1,3,2,2] 這個(gè)數(shù)組生成的柱狀圖
- 每一行的柱狀圖 利用3.a求出最大矩形
public int maximalRectangle(char[][] matrix) {
int m = matrix.length;
if(m == 0) return 0;
int n = matrix[0].length;
int[] heights = new int[n];
int maxArea = 0;
for(int i = 0 ; i < m ; i++ ){
for(int j = 0 ; j < n ; j++){
if(matrix[i][j] == '0') heights[j] = 0;
else heights[j] += 1;
}
maxArea = Math.max(maxArea , getMaxArea(heights) );
}
return maxArea;
}
public int getMaxArea(int[] heights){
//參考上題
}
- 給定一個(gè)非空的整數(shù)數(shù)組蟀苛，返回其中出現(xiàn)頻率前 k 高的元素
輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]
結(jié)合HashMap 和 堆 實(shí)現(xiàn)
class Solution {
//記錄數(shù)組中元素及其對(duì)應(yīng)出現(xiàn)的次數(shù)
Map<Integer , Integer> map = new HashMap<>();
public int[] topKFrequent(int[] nums, int k) {
int[] heap = new int[k];
for(int i : nums){
map.put(i , map.getOrDefault(i,0) + 1);
}
Iterator it = map.keySet().iterator();
int i = 0;
while(it.hasNext()){
// 先初始化一個(gè)大小為k的堆，當(dāng)堆中元素個(gè)數(shù)為k時(shí)逮诲，建立小根堆
if( i < k){
heap[i] = (Integer)it.next();
i++;
if(i == k){
for(int j = k/2 -1 ; j >= 0 ; j--){
heapSort(heap,j);
}
}
}else{ //小根堆建好后 帜平，對(duì)于每個(gè)新遍歷的元素與堆頂比較，如果比堆頂大梅鹦，替換
//堆頂裆甩，重新維持小根堆
int key = (Integer)it.next();
if(map.get(key) > map.get(heap[0])) heap[0] = key;
heapSort(heap , 0);
}
}
return heap;
}
//維持小根堆
//注意，堆中元素比較是比較它們出現(xiàn)的次數(shù)齐唆，即該元素在map中對(duì)應(yīng)的value
public void heapSort(int[] heap , int i){
int temp = heap[i];
for(int j = 2*i + 1 ; j < heap.length ; j = 2*j + 1){
if(j+1 < heap.length && map.get(heap[j+1]) < map.get(heap[j])) j++;
if(map.get(heap[j]) < map.get(temp)){
heap[i] = heap[j];
i = j;
}else break;
}
heap[i] = temp;
}
}
