leetcode算法之棧和隊列

今天來盤一盤 **棧以及隊列 ** 這兩類題目

使用python刷題分類整理的筆記,請參考: https://github.com/lxztju/leetcode-algorithm/tree/v1

棧和隊列

棧: 先進先出

隊列: 先進後出

利用這兩類資料結構的特性解題.

其中一類非常經典的題目是: 單調棧(leetcode496題, 經典題目).

單調遞減棧, 是指針對每一個待周遊的元素x, 将x與棧頂元素相比, 如果大于棧頂元素将棧頂元素出棧, 重新循環對比,直到小于棧頂元素,然後将x入棧.
單調遞增棧: 同理分析

232 用棧實作隊列 (Easy)
225 用隊列實作棧 (Easy)
155 最小棧 (Easy)
20 有效的括号 (Easy)
1021 删除最外層的括号 (easy)
496 下一個更大元素 I (easy)
503 下一個更大元素 II (Medium)
739 每日溫度 (Medium)

232 用棧實作隊列 (Easy)

題解: 兩個棧實作
- 棧的特點時先進後出, 而隊列是先進先出
- 使用兩個棧實作先進先出
- stackin控制入隊, stackout控制出隊
- 當入隊時,直接壓入stackin即可
- 出隊時, 當stackout為空時,将stackin中的元素依次彈出壓入stackout中, 然後執行stackout的出棧也就是出隊操作.
示例

先入隊[1,2], 然後執行一次出隊, 再入隊[3,4], 然後執行兩次出隊

入隊之後stackin為[1,2], stackout為空
執行出隊時,将stackin中元素依次壓入stackout中, 此時stackout為[2,1], 出隊1, stackout為[2], stackin為空
再次入隊, stackin為[3,4], 此時stackout為[2]
執行第一次出隊時, stackout非空直接出隊2, 此時stackin為[3,4], stackout為空
當再次執行出隊時, stackout為空,與第二步相同.

class MyQueue {
public:
    stack<int> stackin;
    stack<int> stackout;
    /** Initialize your data structure here. */
    MyQueue() {

    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        stackin.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        // 如果stackout為空,将stackin中的元素依次放入stackout
        if(stackout.empty())
            while (!stackin.empty() ){
                int tmp = stackin.top();
                stackin.pop();
                stackout.push(tmp);
            }
        // 傳回stackout的棧頂元素
        int tmp = stackout.top();
        stackout.pop();
        return tmp;
    }
    
    /** Get the front element. */
    int peek() {
        // 如果stackout為空,将stackin中的元素依次放入stackout
        if(stackout.empty())
            while (!stackin.empty() ){
                int tmp = stackin.top();
                stackin.pop();
                stackout.push(tmp);
            }
        // 傳回stackout的棧頂元素
        return stackout.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        if (stackin.empty() && stackout.empty())
            return true;
        else
            return false;
    }
};

225 用隊列實作棧 (Easy)

題解: 兩個隊列實作
- 棧是先進後出的, 隊列是先進先出的.
- 使用隊列實作棧就是要将入隊的元素,放置在隊首.
- 這樣出棧時, 直接使用隊列出隊實作.
q1存儲棧中的元素, q2作為入棧時的輔助棧
入棧時,先将元素入隊到q2, 然後将q1中的元素出隊并放入q2中, 此時q2隊首的元素即為棧頂元素, 将q1與q2互換, q2始終作為輔助棧.

class MyStack {
public:
    /** Initialize your data structure here. */
    queue<int> q1;
    queue<int> q2;
    MyStack() {
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        q2.push(x);
        while(!q1.empty()){
            q2.push(q1.front());
            q1.pop();
        }
        swap(q1, q2);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int tmp = q1.front();
        q1.pop();
        return tmp;
    }
    
    /** Get the top element. */
    int top() {
        return q1.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return q1.empty();
    }
};

155 最小棧 (Easy)

題解: 輔助棧
- 采用另外的一個輔助棧s2
- 每次s1入棧出棧時,均在s2的對應位置存入此時對應的最小值
- 對于輔助棧s2的操作, 對于一個待入棧的元素x, 如果其大于s2的棧頂,就在s2中再次壓入棧頂元素, 否則壓入x

class MinStack {
public:
    stack<int> s1;
    stack<int> s2;  // 輔助棧
    /** initialize your data structure here. */

    MinStack() {
    }
    
    void push(int x) {
        s1.push(x);
        if (s2.empty())
            s2.push(x);
        else{
            int tmp = s2.top();
            if (x <= tmp)
                s2.push(x);
            else
                s2.push(tmp);
        }
    }
    
    void pop() {
        s1.pop();
        s2.pop();
    }
    
    int top() {
        return s1.top();
    }
    
    int getMin() {
        return s2.top();
    }
};

20 有效的括号 (Easy)

題解
- 最經典的一道使用棧的題目
- 遇到左括号直接入棧, 遇到右括号,左括号出棧對比

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> parentheses = {{'(', ')'}, {'[', ']'}, {'{', '}'}};  // 字典
        stack<char> stack1;
        for (auto s1: s){
            // s1為右括号
            if (parentheses.find(s1) == parentheses.end()){
                // 如果棧為空, 傳回false
                if (stack1.empty()) return false;
                else{
                    char tmp = stack1.top();
                    stack1.pop();
                    // 如果棧頂元素與s1不對應, 傳回false
                    if (parentheses[tmp] != s1) return false;
                }
            }
            // s1為左括号, 入棧
            else{
                stack1.push(s1);
            }
        }
        //最後棧為空傳回true, 否則傳回false.
        if (!stack1.empty()) return false;
        else return true;
    }
};

1021 删除最外層的括号 (easy)

題解
- 括号的比對, 要使用棧
- 周遊字元串
- 如果遇到左括号直接入棧, 如果此時棧中有超過1個左括号, 說明這個左括号需要保留
- 如果遇到右括号, 左括号對應出棧, 如果此時棧中依然存在左括号, 那麼這個右括号需要保留
- 否則不保留.

class Solution {
public:
    string removeOuterParentheses(string S) {
        string res;
        stack<char> stack1;
        for (auto s1: S){
            if (s1 == '('){
                stack1.push(s1);
                if (stack1.size() > 1)
                    res += s1;
            }
            else{
                stack1.pop();
                if (stack1.size() >= 1)
                    res += ')';
            }
        }
        return res;
    }
};

496 下一個更大元素 I (easy)

題解: 暴力法
- 利用map存儲nums2中每個元素與索引的位置
- 對于nums1中的每個元素, 從nums2中與其對應的下一個位置開始查找

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        unordered_map<int, int> nums2Index;
        for (int i = 0; i< nums2.size(); i++){
            nums2Index.insert(make_pair(nums2[i], i));
        }
        // 暴力法
        for(int i = 0; i< nums1.size(); i++){
            bool flag = true;
            for (int j = nums2Index[nums1[i]]; j< nums2.size(); j++){
                if (nums2[j] > nums1[i]){
                    res.push_back(nums2[j]);
                    flag = false;
                    break;
                }
            }
            if (flag) res.push_back(-1);
        }
        return res;
    }
};

題解2: 單調棧
- 依次周遊數組nums1, 如果棧為空将nums1[i]入棧
- 如果nums[i+1] 大于棧頂元素, 就将棧頂出棧, 此時對應棧頂的下一個大的元素就是nums[i+1]
- 如果nums[i+1] 不大于nums[i], 就将nums[i+1]入棧, 直到找到nums[j]大于棧頂就依次比較出棧.

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        unordered_map<int, int> nums2Index;

        // 單調棧
        stack<int> decendStack;
        for (int i = 0; i < nums2.size(); i++){
            if (decendStack.empty() || decendStack.top() >= nums2[i])
                decendStack.push(nums2[i]);
            else{
                while (!decendStack.empty() && decendStack.top() < nums2[i]){
                    nums2Index[decendStack.top()] = nums2[i];
                    decendStack.pop();
                }
                decendStack.push(nums2[i]);
            }
        }

        // 最終如果棧非空, 那麼棧中下一個最大的元素不存在
        while (! decendStack.empty()){
            int tmp = decendStack.top();
            decendStack.pop();
            nums2Index[tmp] = -1;        
        }


        for(int i = 0; i< nums1.size(); i++){
            res.push_back(nums2Index[nums1[i]]);
        }
        return res;
    }
};

503 下一個更大元素 II (Medium)

題解: 單調棧
- 循環數組, 那麼直接周遊兩遍就可以了
- 還有一個不同點就是,這裡可能會出現相同的元素, 是以使用map會導緻錯誤(這裡我就搞錯了依次)
- 周遊數組兩次，每次pop之前都去更新一下res

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> stk;
        vector<int> res(nums.size(), -1);
        for(int i = 0; i < nums.size() * 2; i++)
        {
            int index = i % nums.size();
            while(!stk.empty() && nums[stk.top()] < nums[index])
            {
                // 如果已經找到了下一個最大的元素, 那麼跳過
                if(res[stk.top()] == -1)
                {
                    res[stk.top()] = nums[index];
                }
                stk.pop();
            }
            stk.push(index);
        }
        return res;
    }
};

739 每日溫度 (Medium)

題解: 單調棧
- 與496題目一樣, 找尋下一個最大的元素
- 不同的是這裡需要儲存的是索引之間的內插補點.

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        vector<int> res(T.size(), 0);
        stack<int> stk;
        // 周遊T
        for (int i = 0; i< T.size(); i++){
            // 如果新的氣溫大于棧頂的氣溫, 那麼儲存需要等待的天數(索引值差)
            // 棧頂出棧
            while(!stk.empty() && T[stk.top()] < T[i]){
                res[stk.top()] = i - stk.top();
                stk.pop();
            }
            stk.push(i);
        }
        return res;
    }
};

leetcode算法之棧和隊列

棧和隊列

232 用棧實作隊列 (Easy)

225 用隊列實作棧 (Easy)

155 最小棧 (Easy)

20 有效的括号 (Easy)

1021 删除最外層的括号 (easy)

496 下一個更大元素 I (easy)

503 下一個更大元素 II (Medium)

739 每日溫度 (Medium)

更多分類刷題資料

繼續閱讀

LeetCode-110-平衡二叉樹-C語言

[轉]ISUP信令的IAM消息詳細内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

27. Remove Element(清單)題目代碼

回溯法迷宮求解

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

LeetCode OJ Binary Tree Right Side View

leetcode809

Linux裝置模型（中）之上層容器

hdu7108哈希