栈/堆/队列刷题(下)

一、数据流中的中位数

解法一:暴力法

class Solution {
    
public: 
    vector<int>data;
    void Insert(int num) {
    
        data.push_back(num);
    }

    double GetMedian() {
    
        sort(data.begin(),data.end());
        int n=data.size();
        if(n&1)//为奇数
            return (double)data[n>>1];//返回中间值
        else//偶数返回中间两数之和除2
            return (double)(data[n>>1]+data[(n-1)>>1])/2;
    }
};

时间复杂度:O(n${\log }_2$n),快速排序
空间复杂度:O(n)

解法二:插入排序

在存值时使用插入排序，存完即排完
lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

class Solution {
    
public:
    #define transfer static_cast<double>
    vector<int>data;
    void Insert(int num) {
    
        if(data.empty())
            data.push_back(num);
        else{
    
            auto it=lower_bound(data.begin(),data.end(),num);
            data.insert(it,num);
        }
    }

    double GetMedian() {
     
        int n=data.size();
        if(n&1)
            return transfer(data[n>>1]);
        else
            return transfer(data[n>>1]+data[(n-1)>>1])/2;
    }

};

时间复杂度：Insert()为O(n),即二分查找的O(${\log }_2$n)和挪动数据的O(n), GetMedian()为O(1)
空间复杂度：O(n)

解法三:堆

• 用两堆存值，大顶堆存小值，顶部最大，小顶堆存大值，顶部最小，中位数就产生在两堆堆顶
• *规定奇数取大顶堆堆顶值，偶数取两堆堆顶平均值，偶数两堆大小应该相同，奇数则不同，大顶堆多一个
• 大顶堆的数据不可能比小顶堆少一个，需要检测，并平衡两堆大小

class Solution {
    
public:
    #define transfer static_cast<double>
    //大顶堆，元素数值较小
    priority_queue<int> min; 
    //小顶堆，元素数值都比大顶堆大
    priority_queue<int, vector<int>, greater<int>> max;
    //维护两个堆，取两个堆顶部即可
    void Insert(int num) {
           
        //先加入较小部分 
        min.push(num);
        //将较小部分的最大值取出，送入到较大部分
        max.push(min.top());  
        min.pop();
        //平衡两个堆的数量
        if(min.size() < max.size()){
      
            min.push(max.top());
            max.pop();
        }        
    }
    double GetMedian() {
    
        return min.size()>max.size()?transfer(min.top()):transfer(min.top()+max.top())/2;
        //奇数个
        if(min.size() > max.size())  
            return (double)min.top();
        else
            //偶数个
            return (double)(min.top() + max.top()) / 2; 
    }
};

时间复杂度：Insert函数)O(${\log }_2$n)，维护堆的复杂度，GetMedian函数O(1），直接访问
空间复杂度：O(n)，两个堆的空间，虽是两个，但是一个堆最多n/2

二、表达式求值

解法一 :栈+递归

• 借助栈实现优先级处理，遇到+正常入栈，-取相反数入栈，*将栈中元素弹出与最后一个元素相乘再入栈，最后将栈中所有元素相加即可
• 括号的处理借助递归将括号内的运算视为子问题

class Solution {
    
public:
    vector<int>fun(string str,int index)
    {
    
        stack<int>s;
        int num=0,i;
        char op='+';
        for(i=index;i<str.length();i++)
        {
    
            //字符化数
            if(isdigit(str[i]))
            {
    
                num=num*10+str[i]-'0';
                if(i!=str.length()-1)
                    continue;
            }
            //遇到'('时，将整个括号当作一个数字处理
            if(str[i]=='(')
            {
    
                vector<int>tmp=fun(str,i+1);
                num=tmp[0];
                i=tmp[1];
                if(i!=str.length()-1)
                    continue;
            }
            switch(op)
            {
    
                case '+':
                    s.push(num);
                    break;
                case '-':
                    s.push(-num);
                    break;
                case '*'://优先计算乘号
                    int ret=s.top();
                    s.pop();
                    s.push(ret*num);
                    break;
            }
            num=0;
            if(str[i]==')')
                break;
            else
                op=str[i];
        }
        int sum=0;
        while(!s.empty())
        {
    
            sum+=s.top();
            s.pop();
        }
        return vector<int>{
    sum,i};//数组第一个元素为运算值，第二个为字符串长度
    }
    int solve(string s) {
    
        // write code here
        return fun(s,0)[0];
    }
};

时间复杂度：O(n)，n为字符串长度，相当于遍历一遍字符串全部元素
空间复杂度：O(n)，辅助栈和递归栈的空间

解法二:双栈法

• 使用两个栈, op保存运算符，val保存数值
  对字符串进行遍历，如果字符为数字，则将连续的数放入val栈，运算符存入op栈
• 如果ops栈为空或者当前字符为’(;或者op栈顶元素为’('，则入栈；
• 如果当前字符为’’，因为’‘优先级比+，-高，所以向后移一位直接将后面连续的数与val栈顶元素相乘放入val
• 如果当前字符为’)'，+，-，末尾，则将val中的两个数进行op栈顶的操作，将结果进栈；
  此时，栈顶元素可能为+，-，*
• 如果当前字符为’);,那么将’('也弹出栈，如果已到结尾，则直接退出循环。
  val栈顶元素即为最终结果。

class Solution {
    
public:
    int solve(string s) {
    
        stack<int> val;
        stack<char> op;
        for(int i=0; i<=s.length();){
    
            if(isdigit(s[i]))
                val.push(to_int(s, i));
            else if(op.empty()||op.top()=='('||s[i]=='(')
                op.push(s[i++]);
            else if(s[i]=='*'){
    
                int v1=val.top(),v2=to_int(s, ++i);
                val.pop();
                val.push(v1*v2);
            }
            else{
    
                int v2=val.top();
                val.pop();
                int v1=val.top();
                val.pop();
                if(op.top()=='+')
                    val.push(v1+v2);
                else if(op.top()=='-')
                    val.push(v1-v2);
                else if(op.top()=='*')
                    val.push(v1*v2);
                op.pop();
                if(s[i]==')'){
    
                    op.pop();
                    i++;
                }
                else if(i==s.length())
                    break;
            }
        }
        return val.top();
    }
    int to_int(string s,int &i){
    
        int tmp=0;
        while(isdigit(s[i]))
            tmp=tmp*10+s[i++]-'0';
        return tmp;
    }
};

时间复杂度:O(n),遍历字符串
空间复杂度:O(n),两个栈的空间加在一起为字符串长度n