秋招算法之——棧、隊列

1. 用隊列實現(xiàn)?；螂p棧實現(xiàn)隊列相關(guān)

  1. 一個隊列實現(xiàn)棧：要彈出，隊尾先存入隊首
class MyStack {

    /*
    一個隊列實現(xiàn)棧功能
    8.23
    */
    LinkedList<Integer> queue;

    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        //入隊尾
        queue.addLast(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        //要彈出棧頂，隊尾先存入隊首
        for(int i=0;i<queue.size()-1;i++){
            queue.addLast(queue.pollFirst());
        }

        return queue.pollFirst();
    }
    
    /** Get the top element. */
    public int top() {
        //要返回棧頂，隊尾先存入隊首
        for(int i=0;i<queue.size()-1;i++){
            queue.addLast(queue.pollFirst());
        }

        //先接收隊首
        int pre = queue.pollFirst();

        //重新入隊尾
        queue.addLast(pre);

        return pre;
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        if(queue.size() == 0){
            return true;
        }else{
            return false;
        }
    }
}
  1. 雙棧實現(xiàn)隊列
class MyQueue {
    /*
    雙棧實現(xiàn)隊列，棧先進(jìn)后出，隊列先進(jìn)先出
    8.23
    */
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();

    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        //stack1直接入棧
        stack1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        //當(dāng)stack2為空stack1不為空時，stack2存入stack1的彈出，實現(xiàn)先進(jìn)先出
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }

        if(stack2.isEmpty()){
            return -1;
        }else{
            return stack2.pop();
        }
    }
    
    /** Get the front element. */
    public int peek() {
        //同pop
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }

        if(stack2.isEmpty()){
            return -1;
        }else{
            return stack2.peek();
        }
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        //判斷stack1和stack2都為空
        return stack1.isEmpty() && stack2.isEmpty();
    }
}
  1. 最小棧：包含min的棧
class MinStack {

    /*
    最小棧：雙棧維護(hù)min
    8.24
    */

    Stack<Integer> stack;
    Stack<Integer> min;

    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
        min = new Stack<>();
    }
    
    public void push(int x) {
        //stack直接存
        stack.push(x);

        //min的棧頂維護(hù)min
        if(min.isEmpty() || min.peek() >= x){
            min.push(x);
        }
    }
    
    public void pop() {
        //如果stack.pop等于min.peek。min彈出棧頂
        if(stack.pop().equals(min.peek())){
            min.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min.peek();
    }
}
  1. 最大隊列：
class MaxQueue {

    /*
    隊列的最大值
    7.27
    */
    
    LinkedList<Integer> queue;
    //max隊首維護(hù)最大值
    LinkedList<Integer> max;

    public MaxQueue() {
        queue = new LinkedList<>();
        max = new LinkedList<>();
    }
    
    public int max_value() {
        //如果queue為空，返回-1，否則返回max隊首
        if(queue.isEmpty()){
            return -1;
        }else{
            return max.peekFirst();
        }
    }
    
    public void push_back(int value) {
        queue.addLast(value);

        //因為max隊列的隊首維護(hù)最大值，如果當(dāng)前元素比隊尾大，彈出隊尾，將當(dāng)前元素入隊尾，形成從大到小排序的隊列
        while(!max.isEmpty() && max.peekLast() <= value){
            max.removeLast();
        }

        max.addLast(value);
    }
    
    public int pop_front() {

        if(queue.isEmpty()){
            return -1;
        }

        //先接收隊列彈出的隊首
        int result = queue.removeFirst();
        //判斷彈出的元素與max隊列維護(hù)的最大值是否相等，如果相等，max隊列也要彈出隊首
        if(result == max.peekFirst()){
            max.removeFirst();
        }
        //返回隊列的彈出
        return result;
    }
}

2. 括號匹配類型

  1. 有效括號(老經(jīng)典了，好幾次筆試都碰到了)
class Solution {
    public boolean isValid(String s) {
        /*
        有效括號
        8.24
        */

        //單調(diào)棧，當(dāng)遇到左半括號時，存入右半括號，如果棧為空，說明沒有存入，如果棧彈出的不等于下一個字符(右半括號)

        Stack<Character> stack = new Stack<>();

        char[] str = s.toCharArray();

        for(int i=0;i<str.length;i++){
            if(str[i] == '('){
                stack.push(')');
            }else if(str[i] == '['){
                stack.push(']');
            }else if(str[i] == '{'){
                stack.push('}');
            }else if(stack.isEmpty() || stack.pop() != str[i]){
                //如果棧為空，說明無法存入右半。如果棧頂不等于下一次(右半括號)，說明無法閉合
                return false;
            }
        }

        return stack.isEmpty();
    }
}
  1. 最長有效括號：
class Solution {
    public int longestValidParentheses(String s) {
        /*
        最長有效括號
        8.23
        */
        
        //先預(yù)存-1，用于判斷字符串是否是"))"類型
        //當(dāng)遇到"("時，先將其索引入棧
        //當(dāng)遇到")"時，彈出棧頂元素，表示已經(jīng)使用右括號匹配左括號，形成一個閉合括號
            //如果彈出之后棧為空，說明字符串可能是:"))"這種形式，表明當(dāng)前右括號無法閉合，將其索引重新入棧
            //如果彈出之后棧不為空，當(dāng)前索引 - 棧頂。如"(()"，當(dāng)遇到)時，彈出棧頂元素1，當(dāng)前索引2 - 0 = 2，就是最長有效括號

        Stack<Integer> stack = new Stack<>();
        stack.push(-1);

        char[] str = s.toCharArray();

        int result = 0;
        
        for(int i=0;i<str.length;i++){
            if(str[i] == '('){
                stack.push(i);
            }else{
                //一定要先彈出
                stack.pop();

                if(stack.isEmpty()){
                    stack.push(i);
                }else{
                    result = Math.max(result,i - stack.peek());
                }
            }
        }

        return result;
    }
}

3. 單調(diào)棧

  1. 驗證棧彈出和棧存入
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        /*
        驗證棧序列
        單調(diào)棧
        8.24
        */

        Stack<Integer> stack = new Stack<>();
        int index = 0;

        //遍歷入棧序列
        for(int i : pushed){        

            //先入棧
            stack.push(i);

            //while循環(huán)判斷，如果相等，彈出棧頂
            while(!stack.isEmpty() && stack.peek() == popped[index]){
                index++;
                stack.pop();
            }    
        }

        return stack.isEmpty();
    }
}
  1. 每日溫度
class Solution {
    public int[] dailyTemperatures(int[] T) {
        /*
        每日溫度
        7.26
        */
        //單調(diào)棧，棧存索引，當(dāng)棧頂比當(dāng)前小時，計算差值

        Stack<Integer> stack = new Stack<>();
        int[] result = new int[T.length];

        for(int i=0;i<T.length;i++){

            //棧比數(shù)組慢，當(dāng)棧頂小于當(dāng)前數(shù)組元素時，說明升溫，彈出棧頂，計算其索引差值，存入到result數(shù)組對應(yīng)的索引位置(不是順序存儲啊)
            while(!stack.isEmpty() && T[i] > T[stack.peek()]){
                int index = stack.pop();
                result[index] = i - index;
            }

            stack.push(i);
        }

        return result;
    }
}
  1. 柱狀圖的最大矩形
class Solution {
    public int largestRectangleArea(int[] heights) {
        /*
        柱狀圖中最大的矩形
        7.24
        */
        //單調(diào)棧，先復(fù)制數(shù)組，在頭尾添加一個高度為1的柱體

        //判斷空
        if(heights.length == 0){
            return 0;
        }

        //復(fù)制數(shù)組，在頭尾插入一個高度為0的主題
        int[] temp = new int[heights.length+2];
        //從1到temp.length
        System.arraycopy(heights,0,temp,1,heights.length);

        Stack<Integer> stack = new Stack<>();
        int result = 0;

        for(int i=0;i<temp.length;i++){

            //while棧頂比當(dāng)前大，找到第一個比當(dāng)前小的柱體，計算其體積
            while(!stack.isEmpty() && temp[i] < temp[stack.peek()]){
                
                int high = temp[stack.pop()];

                int widht = i - stack.peek() - 1;

                result = Math.max(high*widht,result);
            }

            stack.push(i);
        }

        return result;
    }
}
  1. 接雨水(解法不屬于單調(diào)棧，但還是一類型的經(jīng)典題目，所以放在一起總結(jié))
class Solution {
    public int trap(int[] height) {
        /*
        接雨水
        7.24
        */
        //左右數(shù)組存最大值，提取左右數(shù)組的最小值，如果最小值比當(dāng)前高度高，疊加雨水量

        //判斷空
        if(height.length == 0){
            return 0;
        }

        int[] left_max = new int[height.length];
        int[] right_max = new int[height.length];

        //從左往右搜，提取最大值，從1開始(0不能存水)
        for(int i=1;i<height.length;i++){
            left_max[i] = Math.max(height[i-1],left_max[i-1]);
        }

        //從右往左搜，提取最大值，從len-2開始(len-1不能存水)
        for(int i=height.length-2;i>=0;i--){
            right_max[i] = Math.max(height[i+1],right_max[i+1]);
        }

        int result = 0;
        //從1到len-2 
        for(int i=1;i<height.length-1;i++){
            int low = Math.min(left_max[i],right_max[i]);

            //如果low比當(dāng)前高度高，說明可以存水，疊加高度差
            if(low > height[i]){
                result += low-height[i];
            }
        }

        return result;
    }
}
  1. 滑動窗口的最大值
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        /*
        滑動窗口的最大值
        8.24
        */

        //創(chuàng)建窗口數(shù)組
        int len = nums.length;
        int[] result = new int[len-k+1];

        //創(chuàng)建隊列
        LinkedList<Integer> queue = new LinkedList<>();

        int index = 0;
        for(int i=0;i<nums.length;i++){
            //隊尾維護(hù)最大值
            while(!queue.isEmpty() && nums[i] > nums[queue.peekLast()]){
                queue.removeLast();
            }

            queue.addLast(i);

            //當(dāng)滑動窗口左邊界等于隊首時，說明要右移，隊列彈出隊首
            if(i-k == queue.peekFirst()){
                queue.removeFirst();
            }

            //存入：當(dāng)形成滑動窗口之后，添加隊首對應(yīng)的元素
            if(i >= k-1){
                result[index++] = nums[queue.peekFirst()];
            }
        }

        return result;
    }
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容