C++算法之数据结构二

妙用数据结构

1.栈和队列

题目一：尝试使用栈（stack）来实现队列（queue）

我们可以用两个栈来实现一个队列：因为我们需要得到先入先出的结果，所以必定要通过一个额外栈翻转一次数组。这个翻转过程既可以在插入时完成，也可以在取值时完成。

class MyQueue{
    stack<int>in,out;
public:
    MyQueue(){};

    void push(int x)
    {
        in.push(x);
    }
    int pop(){
        in2out();
        int x=out.top();
        out.pop();
        return x;
    }
    int peek(){
        in2out();
        return out.top();
    }
    void in2out(){
        if(out.empty()){
            while(!in.empty()){
                int x=in.top();
                in.pop();
                out.push(x);
            }
        }
    }
    bool empty(){
        return in.empty() && out.empty();
    }
};

题目二：设计一个最小栈，除了需要支持常规栈的操作外，还需要支持在 O(1) 时间内查询栈内最小值的功能

//调用样例
Mintack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // Returns -3.
minStack.pop();
minStack.top(); // Returns 0.
minStack.getMin(); // Returns -2.

可以额外建立一个新栈，栈顶表示原栈里所有值的最小值。每当在原栈里插入一个数字时，若该数字小于等于新栈栈顶，则表示这个数字在原栈里是最小值，我们将其同时插入新栈内。每当从原栈里取出一个数字时，若该数字等于新栈栈顶，则表示这个数是原栈里的最小值之一，我们同时取出新栈栈顶的值。

class MinStack {
    stack<int> s, min_s;
public:
    MinStack() {}
    void push(int x) {
        s.push(x);
        if (min_s.empty() || min_s.top() >= x) {
        min_s.push(x);
        }
    }
    void pop() {
        if (!min_s.empty() && min_s.top() == s.top()) {
            min_s.pop();
        }
        s.pop();
    }
    int top() {
        return s.top();
    }
    int getMin() {
        return min_s.top();
    }
};

题目三：给定一个只由左右原括号、花括号和方括号组成的字符串，求这个字符串是否合法。合法的定义是每一个类型的左括号都有一个右括号一一对应，且括号内的字符串也满足此要求。

括号匹配是典型的使用栈来解决的问题。我们从左往右遍历，每当遇到左括号便放入栈内，遇到右括号则判断其和栈顶的括号是否是统一类型，是则从栈内取出左括号，否则说明字符串不合法。

bool isVaild(string s){
    stack<char>parsed;
    for(int i=0;i<s.length();++i)
    {
        if(s[i] == '{' || s[i] == '[' || s[i] ==  '(' )
        {
            parsed.push(s[i]);
        }
        else{
            if(parsed.empty()){
                return false;
            }
            char c = parsed.top();
            if((s[i] == '}' && c== '{') ||(s[i] == ']' && c== '(') || (s[i] == ')' && c== '(')
            {
                parsed.pop();
            }
            else{
                return false;
            }
        }
    }
    return parsed.empty();
}         

2.单调栈

单调栈通过维持栈内值的单调递增（递减）性，在整体 O(n) 的时间内处理需要大小比较的问题。

题目一：给定每天的温度，求对于每一天需要等几天才可以等到更暖和的一天。如果该天之后不存在更暖和的天气，则记为 0。

//输入输出样例：
Input: [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]

我们可以维持一个单调递减的栈，表示每天的温度；为了方便计算天数差，我们这里存放位置（即日期）而非温度本身。我们从左向右遍历温度数组，对于每个日期 p，如果 p 的温度比栈顶存储位置 q 的温度高，则我们取出 q，并记录 q 需要等待的天数为 p − q；我们重复这一过程，直到 p 的温度小于等于栈顶存储位置的温度（或空栈）时，我们将 p 插入栈顶，然后考虑下一天。
在这个过程中，栈内数组永远保持单调递减，避免了使用排序进行比较。最后若栈内剩余一些日期，则说明它们之后都没有出现更暖和的日期。

vector<int>dailyTemperatures(vector<int>&temperatures){
    int n=temperatures.size();
    vector<int>ans(n);
    stack<int>indices;
    for(int i=0;i<n;++i)
    {
        while(!indices.empty()){
            int pre_index = indices.top();
            if(temperatures[i] <= temperatures[pre_index])
            {
                break;
            }
            indices.pop();
            ans[pre_index] = i - pre_index;
        }
        indices.push(i);
    }
    reuturn ans;
}

3.优先队列

优先队列（priority queue）可以在 O(1) 时间内获得最大值，并且可以在 O(log n) 时间内取出最大值或插入任意值。

优先队列常常用堆（heap）来实现。堆是一个完全二叉树，其每个节点的值总是大于等于子节点的值。实际实现堆时，我们通常用一个数组而不是用指针建立一个树。这是因为堆是完全二叉树，所以用数组表示时，位置 i 的节点的父节点位置一定为 i/2，而它的两个子节点的位置又一定分别为 2i 和 2i+1。

以下是堆的实现方法，其中最核心的两个操作是上浮和下沉：如果一个节点比父节点大，那么需要交换这个两个节点；交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，我们称之为上浮；类似地，如果一个节点比父节小，也需要不断地向下进行比较和交换操作，我们称之为下沉。如果一个节点有两个子节点，我们总是交换最大的子节点。

//实现：
vector<int>heap;
//获得最大值
void top(){
    return heap[0];
}

//插入任意值，把新的数字放在最后一位，然后上浮
void push(int k)
{
    heap.push_back(k);
    swim(heap.size()-1);
}

//删除最大值，把最后一个数字挪到开头
void pop()
{
    heap[0]=heap.back();
    heap.pop_back();
    sink(0);
}

//上浮
void swim(int pos)
{
    while(pos>1 && heap[pos/2] < heap[pos])){
        swap(heap[pos/2],heap[pos];
        pos/=2;
    }
}

//下沉
void sink(int pos)
{
    while(2*pos <= N)
    {
        int i = 2*pos;
        if(i < N && heap[i] < heap{i+1]) 
            ++i;
        if(heap[pos] >= heap[i])
            break;
        swap(heap[pos],heap[i]);
        pos=i;
    }
}

通过将算法中的大于号和小于号互换，我们也可以得到一个快速获得最小值的优先队列。另外，正如我们在 STL 章节提到的那样，如果我们需要在维持大小关系的同时，还需要支持查找任意值、删除任意值、维护所有数字的大小关系等操作，可以考虑使用 set 或 map 来代替优先队列。

题目一：给定 k 个增序的链表，试将它们合并成一条增序链表。

这里展示一个速度比较快的方法，即把所有的链表存储在一个优先队列中，每次提取所有链表头部节点值最小的那个节点，直到所有链表都被提取完为止。注意因为 Comp 函数默认是对最大堆进行比较并维持递增关系，如果我们想要获取最小的节点值，则我们需要实现一个最小堆，因此比较函数应该维持递减关系，所以 operator() 中返回时用大于号而不是等增关系时的小于号进行比较。

struct Comp{
    bool operator() (ListNode*l1,ListNode*l2)
    {
        return l1->val > l2->val;
    }
};

ListNode* mergeKLists(vector<ListNode*>&lists)
{
    if(lists.empty()) return nullptr;
    priority_queue<ListNode*,vector<ListNode*>,Comp>q;
    for(ListNode* list:lists)
    {
        if(list){
            q.push(list);
        }
    }
    ListNode* dummy = new ListNode(0), *cur = dummy;
    while(!q.empty())
    {
        cur->next = q.top();
        q.pop();
        cur = cur->next;
        if(cur->next)
        {
            q.push(cur->next);
        }
    }
    return dummy->next;
}

题目二：给定建筑物的起止位置和高度，返回建筑物轮廓（天际线）的拐点。

我们可以使用优先队列储存每个建筑物的高度和右端（这里使用 pair，其默认比较函数是先比较第一个值，如果相等则再比较第二个值），从而获取目前会拔高天际线、且妨碍到前一个建筑物（的右端端点）的下一个建筑物。

vector<vector<int>> getSkyline(vector<vector<int>>&buildings)
{
    vector<vector<int>>ans;
    priority_queue<pair<int,int>>max_heap;//高度、右端
    int i=0,len=buildings.size();
    int cur_x,cur_h;
    while(i<len || !max_heap.empty())
    {
        if(max_heap.empty() || i<len && buildings[i][0] <= max_heap.top().second)
        {
            cur_x=buildings[i][0];
            while(i < len && cur_x == buildings[i][0])
            {
                max_heap.emplace(buildings[i][2],buildings[i][1]);
                ++i;
            }
        }
        else{
            cur_x=max_heap.top().second;
            while(!max_heap.empty() && cur_x >= max_heap.top().second)
            {
                max_heap.pop();
            }
        }
        cur_h=(max_heap.empty()) ? 0 : max_heap.top().first;
        if(ans.empty() || cur_h != ans.back()[1])
        {
            ans.push_back({cur_x,cur_h});
        }
    }
    return ans;
}

4.双端队列

题目一：给定一个整数数组和一个滑动窗口大小，求在这个窗口的滑动过程中，每个时刻其包含的最
大值。

我们可以利用双端队列进行操作：每当向右移动时，把窗口左端的值从队列左端剔除，把队列右边小于窗口右端的值全部剔除。这样双端队列的最左端永远是当前窗口内的最大值。另外，这道题也是单调栈的一种延申：该双端队列利用从左到右递减来维持大小关系。

vector<int>maxSlidingWindow(vector<int>&nums,int k)
{
    deque<int>dq;
    vector<int>ans;
    for(int i=0;i<nums.size();++i)
    {
        if(!dq.empty() && dq.front() == i-k)
        {
            dq.pop_front();
        }
        while(!dq.empty() && nums[dq.back()] < nums[i])
        {
            dq.pop_back();
        }
        dq.push_back(i);
        if(i >= k-1)
        {
            ans.push_back(nums[dq.front()]);
        }
    }
    return ans;
}