date: 2020/01/11

基本概念


844比较含退格的字符串(简单)

https://leetcode-cn.com/problems/backspace-string-compare/

从后往前遍历,遇#退格,否则检查字符是否匹配

// 双指针
bool backspaceCompare(string S, string T) {
    int iS = S.size() - 1, iT = T.size() - 1;
    int bS = 0, bT = 0;  // !!用于记录当前未应用的退格数量,不能检测到退格符就直接应用(要考虑连续退格的情况)
    
    while(iS >= 0 || iT >= 0){  // 两个字符串都需要完整遍历
        if(iS >= 0 && S[iS] == '#'){   // S出现退格
            iS--; bS++;
        }else if(iT >= 0 && T[iT] == '#'){   // T出现退格
            iT--; bT++;
        }else if(bS > 0){   // S应用退格
            iS--; bS--;
        }else if(bT > 0){   // T应用退格
            iT--; bT--;
        }else{   // 非退格
            if(iS < 0 || iT < 0 || S[iS] != T[iT])  // S或T单方面遍历完毕,或当前字符不匹配
                return false;
            iS--; iT--;
        }
    }
    return true;
}


232用栈实现队列(简单)

https://leetcode-cn.com/problems/implement-queue-using-stacks/

stack<int> data;  // data.top() is the rear of queue

void push(int x){
    data.push(x);
}

int pop(){
    stack<int> tmp;
    // 翻转
    while(!data.empty()){
        tmp.push(data.top());
        data.pop();
    }
    // 取出栈顶(即原栈底)
    int res = tmp.top();
    tmp.pop();
    // 翻转(恢复)
    while(!tmp.empty()){
        data.push(tmp.top());
        tmp.pop();
    }
    return res;
}
stack<int> s1;   // s1.top() is the rear of queue
stack<int> s2;   // s2.top() is the front of queue

void push(int x){
    s1.push(x);
}

int pop(){
    if(s2.empty()){
        while(!s1.empty()){
            s2.push(s1.top());
            s1.pop();
        }
    }
    int res = s2.top();
    s2.pop();
    return res;
}


225用队列实现栈(简单)

https://leetcode-cn.com/problems/implement-stack-using-queues/

queue<int> data;  // data.front() is the bottle of stack

void push(int x) {
    data.push(x);
}

int pop() {
    for(int i = 0; i < data.size() - 1; i++){
        data.push(data.front());
        data.pop();
    }
    int res = data.front();
    data.pop();
    return res;
}

int top() {
    int res;
    for(int i = 0; i < data.size(); i++){
        res = data.front();
        data.push(res);
        data.pop();
    }
    return res;
}


020有效括号(简单)

https://leetcode-cn.com/problems/valid-parentheses/

符号栈:空间O(n)时间O(n)


703数据流中的第k大元素(简单)

https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/

class KthLargest {
private:
    priority_queue<int, vector<int>, greater<int>> pq;
    int k;
public:
    KthLargest(int _k, vector<int>& nums) {
        k = _k;
        for(int i = 0; i < nums.size(); i++)
            add(nums[i]);
    }
    
    int add(int val) {
        if(pq.size() < k)
            pq.push(val);
        else if(val > pq.top()){
            pq.pop();
            pq.push(val);
        }
        return pq.top();
    }
};


239滑动窗口最大值(困难)

https://leetcode-cn.com/problems/sliding-window-maximum/

首先定义队列清理操作clean:清理滑出窗口的元素,清理小于新加入窗口的元素的所有元素

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> res;   // 空间O(N-k+1)
    deque<int> win;    // 存窗口里的数值,空间O(k);双向队列,back入队,front出队,皆为O(1)时间
    for(int i = 0; i < nums.size(); i++){
        // 清理队列
        if(i >= k && win.front() == nums[i-k])   // 去掉滑出窗口的元素
            win.pop_front();
        while(!win.empty() && win.back() < nums[i])   // 清理小于当前值的所有元素(注意不能是<=,否则可能之后去除滑出窗口元素时误把新增当前元素给去掉了)
            win.pop_back();
        // 当前元素入队
        win.push_back(nums[i]);
        // 添加输出
        if(i >= k - 1)
            res.push_back(win.front());
    }
    return res;
}


#1

image.png

#2

image.png

#3

image.png

#4

image.png

#5

image.png

#6

image.png


面试题59 队列的最大值II(中等)

https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/

class MaxQueue {
private:
    deque<int> max_dq;  // front最大,单调递减
    queue<int> data;    // 常规队列
public:
    MaxQueue() {}
    
    int max_value() {
        return (max_dq.empty()) ? -1 : max_dq.front();
    }
    
    void push_back(int value) {
        data.push(value);
        while(!max_dq.empty() && max_dq.back() < value)
            max_dq.pop_back();
        max_dq.push_back(value);
    }
    
    int pop_front() {
        if(data.empty())
            return -1;
        
        int res = data.front();
        data.pop();
        if(res == max_dq.front())
            max_dq.pop_front();
        return res;
    }
};