leetcode-常规 - 12. 栈和队列 - 《算法刷题》

12.1 232. 用栈实现队列

class MyQueue {
public:
    //用两个栈模拟，一个存push的，一个将pop出来的存起来
    stack<int> stIn;
    stack<int> stOut;
    MyQueue() {
    }
    void push(int x) {
        stIn.push(x);
    }
    int pop() {
        if(stOut.empty()){
            while(!stIn.empty()){
                int x=stIn.top();                
                stOut.push(x);
                stIn.pop();
            }
        }
        int x=stOut.top();
        stOut.pop();
        return x;        
    }
    int peek() {
        int x=this->pop();
        stOut.push(x);
        return x;  
    }
    bool empty() {
        return stIn.empty()&&stOut.empty();
    }
};
/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

12.2 225. 用队列实现栈

class MyStack {
public:
    queue<int> que;
    MyStack() {
    }
    void push(int x) {
        que.push(x);
    }
    int pop() {
        int size=que.size();
        size--;
        while(size--){
            int x=que.front();
            que.push(x);
            que.pop();
        }
        int x=que.front();
        que.pop();
        return x;
    }
    int top() {
        return que.back();
    }
    bool empty() {
        return que.empty();
    }
};
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

12.3 20. 有效的括号

class Solution {
public:
    bool isValid(string s) {
        stack<int> st;
        for(int i=0;i<s.length();i++){
            if(s[i]=='('){
                st.push(')');
            }else if(s[i]=='['){
                st.push(']');
            }else if(s[i]=='{'){
                st.push('}');
            }else if(!st.empty()&&st.top()==s[i]){
                st.pop();
            }else{
                return false;
            }
        }
        return st.empty();
    }
};

12.4 921. 使括号有效的最少添加

class Solution {
public:
    int minAddToMakeValid(string s) {
        int need=0;//右括号的需求
        int needLeft=0;//左括号的需求
        for(int i=0;i<s.length();i++){
            if(s[i]=='('){
                need++;
            }else if(s[i]==')'){
                need--;
                if(need==-1){
                    need=0;
                    needLeft++;
                }
            }
        }
        return need+needLeft;
    }
};

12.5 1541. 平衡括号字符串的最少插入次数

class Solution {
public:
    int minInsertions(string s) {
        int needRight=0,result=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                needRight+=2;
                if(needRight%2==1){
                    //奇数时，要插入一个右括号
                    result++;
                    //右括号需求-1
                    needRight--;
                }
            }else if(s[i]==')'){
                needRight--;
                if(needRight==-1){
                    needRight=1;
                    result++;
                }
            }
        }
        return needRight+result;
    }
};

12.6 1047. 删除字符串中的所有相邻重复项

//栈
class Solution {
public:
    string removeDuplicates(string s) {
        stack<int> st;
        for(int i=0;i<s.length();i++){
            if(st.empty()||s[i]!=st.top()){
                st.push(s[i]);
            }else{
                st.pop();
            }
        }
        string result="";
        while(!st.empty()){
            result+=st.top();
            st.pop();
        }
        reverse(result.begin(),result.end());
        return result;
    }
};
//字符串
class Solution {
public:
    string removeDuplicates(string s) {
        string result="";
        for(int i=0;i<s.length();i++){
            if(result.empty()||s[i]!=result.back()){
                result.push_back(s[i]);
            }else{
                result.pop_back();
            }
        }
        return result;
    }
};

12.7 150. 逆波兰表达式求值

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(int i=0;i<tokens.size();i++){
            if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/"){
                int num2=st.top();
                st.pop();
                int num1=st.top();
                st.pop();
                if(tokens[i]=="+") st.push(num1+num2);
                else if(tokens[i]=="-") st.push(num1-num2);
                else if(tokens[i]=="*") st.push(num1*num2);
                else if(tokens[i]=="/") st.push(num1/num2);
            }else{
                st.push(stoi(tokens[i]));
            }
        }
        return st.top();
    }
};

12.8 239. 滑动窗口最大值

class Solution {
private:
    class MyQueue{
    //保证队列第一个元素为最大的,单调队列
    public:
        deque<int> d;
        void push(int value){
            //比自己小的元素都删去
            while(!d.empty()&&value>d.back()){
                d.pop_back();
            }
            d.push_back(value);
        }
        void pop(int value){
            if(!d.empty()&&value==d.front()){
                d.pop_front();
            }
        }
        int getMax(){
            return d.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue mq;
        vector<int> result;
        for(int i=0;i<k;i++){
            mq.push(nums[i]);         
        }
        result.push_back(mq.getMax());
        for(int i=k;i<nums.size();i++){
            mq.pop(nums[i-k]);            
            mq.push(nums[i]);
            result.push_back(mq.getMax());
        }
        return result;
    }
};

12.9 347. 前 K 个高频元素

class Solution {
public:
    class myComparison{
    public:
        bool operator()(const pair<int,int>& a,const pair<int,int>& b){
            return a.second>b.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        //map的key为num,value为freq
        unordered_map<int,int> map;
        for(int i=0;i<nums.size();i++){
            map[nums[i]]++;
        }
        //根据map的freq进行排序，小堆树
        //定义 priority_queue<数据类型、底层容器、比较函数>
        priority_queue<pair<int,int>,vector<pair<int,int>>,myComparison> pri_que;
        for(auto it=map.begin();it!=map.end();it++){
            pri_que.push(*it);
            if(pri_que.size()>k){
                pri_que.pop(); //满k个后弹出freq低的
            }
        }
        //输出priority_queue剩下的k个
        vector<int> result(k);
        for(int i=k-1;i>=0;i--){
            result[i]=pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};

12.10 496. 下一个更大元素 I

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        unordered_map<int,int> map;
        //找num2中每个元素右边第一大的数 存入hash_table
        for(int i=nums2.size()-1;i>=0;i--){
            while(!st.empty()&&nums2[i]>=st.top()){
                st.pop();
            }  
            //先取出最大的数，在存入本数          
            map[nums2[i]]=st.empty()?-1:st.top();
            st.push(nums2[i]);
        }
        //nums1中的数，在hash_table中查找
        vector<int> result(nums1.size());
        for(int i=0;i<nums1.size();i++){
            result[i]=map[nums1[i]];
        }
        return result;
    }
};

12.11 503. 下一个更大元素 II

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n=nums.size();
        stack<int> st;
        vector<int> result(n);
        for(int i=2*n-1;i>=0;i--){
            while(!st.empty()&&nums[i%n]>=st.top()){
                st.pop();
            }
            result[i%n]=st.empty()?-1:st.top();
            st.push(nums[i%n]);
        }
        return result;
    }
};

12.12 739. 每日温度

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n=temperatures.size();
        stack<int> st;
        vector<int> result(n);
        for(int i=n-1;i>=0;i--){
            while(!st.empty()&&temperatures[i]>=temperatures[st.top()]){
                st.pop();
            }
            result[i]=st.empty()?0:(st.top()-i);
            st.push(i);
        }
        return result;
    }
};

12.13 316. 去除重复字母

class Solution {
public:
    string removeDuplicateLetters(string s) {
        stack<char> st;   
        unordered_set<char> inStack;  //记录元素是否出现
        unordered_map<char,int> count;  //记录出现次数
        for(char c:s){
            count[c]++;
        }
        for(char c:s){
            count[c]--;
            //如果没有出现记录
            if(inStack.find(c)==inStack.end()){
                //比较该元素与栈顶元素的次序，判断是否需要弹出
                while(!st.empty()&&st.top()>c&&count[st.top()]!=0){
                    //如果之后不在出现该元素,不弹出，还出现的话，就弹出
                    inStack.erase(st.top());  //删除出现记录
                    st.pop();
                }                
                inStack.insert(c); //增加出现记录
                st.push(c);
            }
        }
        string result="";
        while(!st.empty()){
            result.push_back(st.top());
            st.pop();
        }
        reverse(result.begin(),result.end());
        return result;
    }
};