第一章 基础数据结构

在常见的数据结构一般包括：链表、栈、队列、串、多维数组、广义表、哈希、树和二叉树、图等。本章主要介绍链表、队列、栈、二叉树、堆。

1.1 链表

链表是用一组任意位置的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以不连续的。它的基本操作有：初始化、添加、遍历、删除、查找、释放等。链表分位单向链表和双向链表，如图：

• 单向链表每个节点有两个部分：指向下一位的指针(next)和数据(data)。
• 双向链表的每个节点有三个部分：指向上一位的指针(pre)、下一位的指针(next)和数据(data)。

C++中，使用链表可以用STL库，也可以自己手写。Python中可以使用自带的List类型以及其他方法实现。这些代码示例会在下方给出。

约瑟夫问题 - 洛谷

以上方例题为例，在这里会给出各种方案的解法

1.1.1 动态链表

动态链表需要临时分配链表节点使用完毕后释放链表节点。动态链表的优点是能及时释放空间，不使用多余内存。缺点是需要管理空间。

// 使用动态链表解决约瑟夫问题
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    node *next;
};

int main()
{
    int n, m;
    cin >> n >> m;
    node *head = new node;  // 创建头结点
    head->data = 1;     // 头结点的数据域存放1
    head->next = NULL;  // 头结点的指针域为空
    node *p = head;    // p指向头结点
    for (int i = 2; i <= n; i++)
    {
        node *q = new node; // 创建新结点
        q->data = i;       // 新结点的数据域存放i
        q->next = NULL;   // 新结点的指针域为空
        p->next = q;    // 将新结点插入到链表尾部
        p = q;
    }
    p->next = head; // 将链表首尾相连
    p = head;
    while (p->next != p)    // 当链表中只有一个结点时，结束循环
    {
        for (int i = 1; i < m - 1; i++) // 找到要删除结点的前一个结点
        {
            p = p->next;
        }
        node *q = p->next;
        p->next = q->next;
        cout << q->data << " ";
        delete q;
        p = p->next;
    }
    cout << p->data << endl;
    delete p;
    return 0;
}

# 使用动态链表解决约瑟夫问题
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

if __name__ == '__main__':
    n,m  = input().split()
    n = int(n)
    m = int(m)
    head = Node(1)
    p = head
    for i in range(2,n+1):
        p.next = Node(i)
        p = p.next
    p.next = head # 将链表首尾相连
    p = head # p指向链表头
    q = None # q指向p的前一个节点
    while p.next != p: # 当链表中只有一个节点时，退出循环
        for i in range(1, m):    # 找到要删除的节点的前一个节点
            q = p
            p = p.next
        print(p.data, end=' ')
        q.next = p.next # 删除节点
        q = p
        p = p.next
    print(p.data)

请注意，这种做法是最标准的做法，但是却也是十分耗时的做法。

1.1.2 静态链表

静态链表具体有两种做法：

1. 定义链表结构体数据，和动态链表结构差不多；
2. 使用一维数组，直接在数组上进行链表操作。

在这里分别给出示例：

// 用结构体数组实现单项静态链表解决约瑟夫问题
#include <bits/stdc++.h>
using namespace std;

const int N = 105;
struct Node {
    int data;
    int next;
} node[N];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {  // 初始化单项静态链表
        node[i].data = i;
        node[i].next = i + 1;
    }
    node[n].next = 1;
    int p = n, q = 1;
    while (p != q) {    // 模拟约瑟夫问题
        for (int i = 1; i < m; ++i) {   // 找到第m个人的前一个人
            p = node[p].next;
            q = node[q].next;
        }
        cout << node[q].data << " ";
        node[p].next = node[q].next;
        q = node[q].next;
    }
    cout << node[p].data << endl;
    return 0;
}

// 用一维数组实现单项静态链表解决约瑟夫问题
#include <bits/stdc++.h>
using namespace std;

int node[150];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n-1; ++i) node[i] = i + 1;
    node[n] = 1;    // 循环链表
    int now = 1, pre = 1;   // now为当前节点，pre为当前节点的前一个节点
    while((n--)>1){ 
        for (int i = 1; i < m; ++i) {   // 找到第m个节点
            pre = now;
            now = node[now];
        }
        cout << now << " ";
        node[pre] = node[now];
        now = node[now];
    }
    cout << now << endl;
    return 0;
}

# 使用静态链表解决约瑟夫问题

if __name__ == '__main__':
    n,m = input().split()
    n = int(n)
    m = int(m)
    L = [None]
    for i in range(1,n+1):
        L.append(i+1)
    L[n] = 1 # 将最后一个元素指向第一个元素
    now = 1
    pre = n
    while now != L[now]:
        for i in range(m-1):
            pre = now
            now = L[now]
        print(now,end=' ')
        L[pre] = L[now]
        now = L[now]
    print(now)

1.1.3 STL链表

在算法和工程项目中常使用C++STL list。list双向链表由标准模板库管理。练习包括list的初始化、插入、删除、遍历、查找、释放等操作。

// 用STL链表解决约瑟夫问题
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    list<int> l;
    for (int i = 1; i <= n; i++) {
        l.push_back(i);
    }
    list<int>::iterator it = l.begin();
    while (l.size() > 1) {
        for (int i = 1; i < m; i++) {
            it++;
            if (it == l.end()) {
                it = l.begin();
            }
        }
        cout << *it << " ";
        it = l.erase(it);
        if (it == l.end()) {
            it = l.begin();
        }
    }
    cout << *it << endl;
    return 0;
}

练习题：

队列安排 - 洛谷

# 洛谷P1160 队列安排
n = int(input())
L = [1] # 每个同学的队列，data是序号
for i in range(n-1):
    k,p = map(int, input().split())
    if p == 1: # 插入右面
        L.insert(L.index(k)+1, i+2)
    else: # 插入左面
        L.insert(L.index(k), i+2)
m = int(input())
for i in range(m):
    x = int(input())
    if x in L:
        L.remove(x)
for i in L:
    print(i, end=' ')

class Node:
    def __init__(self, date, prev, next):
        self.date = date
        self.prev = prev
        self.next = next
        self.flag = True

N = int(input())
a = [None] * (N + 1)
a[0] = Node(0, a[0], a[0])
a[1] = Node(1, a[0], a[0])
a[0].next = a[1]
a[0].prev = a[1]
for i in range(2, N + 1):
    k, p = map(int, input().split())
    if p == 0:
        a[i] = Node(i, a[k].prev, a[k])
        a[k].prev.next = a[i]
        a[k].prev = a[i]
    else:
        a[i] = Node(i, a[k], a[k].next)
        a[k].next.prev = a[i]
        a[k].next = a[i]
M = int(input())
for i in range(M):
    x = int(input())
    a[x].flag = False

cur = a[0]
while cur.next != a[0]:
    cur = cur.next
    if cur.flag != False:
        print(cur.date, end=" ")

力扣

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def reversePrint(self, head: ListNode):
        res = []
        while head != None:
            res.append(head.val)
            head = head.next
        res.reverse()
        return res

if __name__ == '__main__':
    head_num = [1,3,2]
    head = ListNode(None)
    p = head
    for i in head_num:
        p.next = ListNode(i)
        p = p.next
    print(Solution.reversePrint(None,head=head.next))

力扣

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        p = head
        cnt = 0
        while p!= None:
            cnt += 1
            p = p.next
        i = 0
        p = head
        while p!= None:
            i += 1
            if i == cnt - k + 1:
                break
            p = p.next
        return p

if __name__ == '__main__':
    L = list([1])
    head = ListNode(None)
    p = head
    for i in L:
        p.next = ListNode(i)
        p = p.next
    print(Solution.getKthFromEnd(None,head.next,2))

力扣

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        p = head
        L = []
        while p != None:
            L.append(p.val)
            p = p.next
        L.reverse()
        res = ListNode(None)
        p = res
        for _ in L:
            p.next = ListNode(_)
            p = p.next
        return res.next

if __name__ == '__main__':
    L = list(range(1,6))
    head = ListNode(None)
    p = head
    for i in L:
        p.next = ListNode(i)
        p = p.next
    print(Solution.reverseList(None,head.next))

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None
        cur = head
        while cur:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre

力扣

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head1 = l1
        head2 = l2
        head = ListNode(None)
        p = head
        while head1 != None and head2 != None:
            if head1.val > head2.val:
                p.next = ListNode(head2.val)
                p = p.next
                head2 = head2.next
            else: 
                p.next = ListNode(head1.val)
                p = p.next
                head1 = head1.next
        left_list = head2 if head1 == None else head1
        p.next = left_list
        return head.next

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        prhead = ListNode(-1)
        cur = prhead
        while l1 and l2:
            if l1.val<=l2.val:
                cur.next = l1
                l1 = l1.next
            elif l1.val> l2.val:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 if l1 else l2
        return prhead.next

力扣

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head : return None
        dic = {}
        cur = head 
        while cur:
            dic[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        while cur:
            dic[cur].next = dic.get(cur.next)
            dic[cur].random = dic.get(cur.random)
            cur = cur.next
        return dic[head]

力扣

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        A, B = headA, headB
        while A != B:
            A = A.next if A else headB
            B = B.next if B else headA
        return A

如果两个链表长度相同，那么它们会在第一次遍历就能找到公共节点。

力扣

class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        cur = head
        p = ListNode(None)
        p.next = cur
        res = p
        while cur:
            if cur.val == val:
                p.next = cur.next
                break
            p = cur
            cur = cur.next
        return res.next

1.2 队列

队列中的数据存储方式是先进先出。队列有两种实现方式：链队列和循环队列。

• 链队列可以看作是单链表的一种特殊情况。
• 循环队列是一种顺序表，用两个指针head和tail指示队头和队尾元素，当量指针走到底时，回到开始的位置。循环队列能够解决溢出的问题。
• 队列和栈的问题是查找较慢，在某些情况下可以用优先队列，让优先级最高先出队列。

在队列的C++代码是很容易实现的：

const int N = 1e5; //定义队列
int que[N], head, tail; //初始化队列
head++; //队首指针后移
que[head];  //队首元素
que[++tail] = data; //队尾插入元素

在平常我们一般使用STL中的queue。

在Python中我们可以用List来近似实现。

1.2.1 STL queue

例题：

[NOIP2010 提高组] 机器翻译 - 洛谷

// 洛谷P1540 机器翻译
#include <bits/stdc++.h>
using namespace std;
int Hash[1003] = {0};
queue<int> mem;
int main() {
    int m, n;
    cin >> m >> n;
    int cnt;    // 查词典的次数
    while(n--) {
        int en;
        cin >> en;
        if (Hash[en] == 0) {
            cnt++;
            mem.push(en);
            Hash[en] = 1;
            if (mem.size() > m) {
                Hash[mem.front()] = 0;
                mem.pop();
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

# 洛谷P1540 机器翻译
m,n = map(int,input().split())
cnt = 0 # 查询次数
L = []
x = map(int,input().split())
for i in x:
    if i not in L:
        cnt += 1
        L.append(i)
        if len(L) > m:  # 如果超过了最大容量，就把最早的那个删掉
            L.pop(0)    # pop()默认删除最后一个元素，pop(0)删除第一个元素
print(cnt)

1.2.2 手写循环队列

// 洛谷P1540 机器翻译
// 使用手写循环队列
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
int Hash[MAXN] = {0};
struct myqueue{ // 定义循环队列
    int data[MAXN];
    int head, tail;
    myqueue() {
        head = 0;
        tail = 0;
    }
    void push(int x) {
        data[tail] = x;
        tail = (tail + 1) % MAXN;
    }
    int front() {
        return data[head];
    }
    void pop() {
        head = (head + 1) % MAXN;
    }
    bool empty() {
        return head == tail;
    }
    void clear() {
        head = 0;
        tail = 0;
    }
    int size() {
        return (tail - head + MAXN) % MAXN;
    }
}Q;
int main() {
    int m, n;
    cin >> m >> n;
    int cnt = 0;
    while(n--) {
        int x;
        cin >> x;
        if(Hash[x] == 0) {
            cnt++;
            if(Q.size() == m) {
                Hash[Q.front()] = 0;
                Q.pop();
            }
            Q.push(x);
            Hash[x] = 1;
        }
    }
    cout << cnt << endl;
    return 0;
}

1.2.3 双端队列和单调队列

双端队列是一种具有队列和栈性质的数据结构，它能在两端进行插入和删除，而且也只能在两端插入和删除。双端队列和Python的List很像。在STL中，它被命名为deque。

双端队列的经典应用是单调队列。单调队列的元素是单调有序的，且元素在队列中的顺序和原来在序列中的顺序一致，单调队列的队头和队尾都能入队和出队。

例题：

滑动窗口 /【模板】单调队列 - 洛谷

// 洛谷P1886 滑动窗口
#include <bits/stdc++.h>
using namespace std;
deque<int> q;
int main() {
    int n, m;
    cin >> n >> m;
    int a[n + 1];
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {  // 单调队列
        while (!q.empty() && a[q.back()] >= a[i]) q.pop_back(); // 保证队列单调递增
        q.push_back(i);
        if(i>=m) {  // 队列中的元素个数大于等于m时，输出队首元素
            while(!q.empty() && q.front()<=i-m) q.pop_front();
            cout << a[q.front()] << " ";    // 输出队首元素
        }
    }
    cout << endl;
    q.clear();
    for (int i = 1; i <= n; ++i) {
        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
        q.push_back(i);
        if(i>=m) {
            while(!q.empty() && q.front()<=i-m) q.pop_front();
            cout << a[q.front()] << " ";
        }
    }
    cout << endl;
    return 0;
}

以取滑动窗口的最小值为例，如果后面加入的值比队列里的小，那么就弹出前面已经存在的大的值，当存储的值达到要求时，每次输出队列最前面的值（这一定是队列中的最小值）。接下来给出Python做法：

# 洛谷P1886 滑动窗口
n,k = map(int,input().split())
a = list(map(int,input().split()))
q = []
for i in range(n):
    while q and a[i] <= a[q[len(q)-1]]:
        q.pop()
    q.append(i)
    if i>=k-1:
        while q and q[0] <= i-k:
            q.pop(0)
        print(a[q[0]],end=' ')
print()
q.clear()
for i in range(n):
    while q and a[i] >= a[q[len(q)-1]]:
        q.pop()
    q.append(i)
    if i>=k-1:
        while q and q[0] <= i-k:
            q.pop(0)
        print(a[q[0]],end=' ')
print()

• 单调队列和最大子序列和问题：

最大子序和问题按子序列有无长度限制可分为两种：

1. 不限制子序列的长度，在所有可能的子序列中寻找一个序列，该子序列和最大。这种问题的求解比较简单，用贪心法和动态规划算法，复杂度都为O(n)。
2. 限制子序列的长度。给定一个限制长度m，找出一段长度不超过m的连续子序列，使他的子序和最大。这种问题用单调队列，复杂度也为O(n)。

Problem - 1003

问题描述：给定一个序列，求最大的子序列和。

1. 使用贪心法：逐个扫描序列中的元素并累加。（目前不要求掌握）

// hdu 1003 求最大子序和，使用贪心法
#include <bits/stdc++.h>
using namespace std;
int main() {
    int t, n, a[100010], sum, max, start, end, temp, temp_start;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cin >> n;
        sum = 0;
        max = -100001;    // max初始化为-100001，因为题目中有负数
        start = 1;
        end = 1;
        temp_start = 1;
        for (int j = 1; j <= n; j++) {  // 从1开始，因为数组下标从1开始
            cin >> a[j];
            sum += a[j];
            if (sum > max) {    // 如果sum大于max，更新max，start，end
                max = sum;
                start = temp_start;
                end = j;
            }
            if (sum < 0) {  // 如果sum小于0，sum置0，temp_start置j+1
                sum = 0;
                temp_start = j + 1;
            }
        }
        cout << "Case " << i << ":" << endl;
        cout << max << " " << start << " " << end << endl;
        if (i != t) {
            cout << endl;
        }
    }
    return 0;
}

# hdu 1003 求最大子序和，使用贪心法
t = int(input())
for i in range(t):
    n,*a = list(map(int, input().split()))
    max_sum = -100001
    start = 1
    end = 1
    temp_start = 1
    sum = 0
    for j in range(n):
        sum += a[j]
        if sum > max_sum:
            max_sum = sum
            start = temp_start
            end = j+1
        if sum < 0:
            sum = 0
            temp_start = j+2
    print("Case {}: {} {} {}".format(i+1, max_sum, start, end))

1. 使用动态规划（目前不要求掌握）

// hdu 1003 求最大子序和，使用动态规划
#include <bits/stdc++.h>
using namespace std;
int dp[100010];
int main() {
    int t;
    cin >> t;
    for(int k = 1; k <= t; k++) {
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++) {
            cin >> dp[i];
        }
        int start = 1, end = 1, p = 1;
        int max = dp[1];
        for(int i = 2; i <= n; i++) {
            if(dp[i] <= dp[i] + dp[i - 1]) {
                dp[i] = dp[i-1] + dp[i];
            }
            else {
                p = i;
            }
            if(dp[i] > max) {
                max = dp[i];
                start = p;
                end = i;
            }
        }
        cout << "Case " << k << ":" << endl;
        cout << max << " " << start << " " << end << endl;
        if(k != t) {
            cout << endl;
        }
    }
}

# hdu 1003 求最大子序和，使用动态规划

t = int(input())
for i in range(t):
    n, *dp = list(map(int, input().split()))
    dp = list(dp)
    max_sum = dp[0]
    start,end,p = 0,0,0
    for j in range(1,n):
        if dp[j] <= dp[j] + dp[j-1]:
            dp[j] = dp[j] + dp[j-1]
        else:
            p = j
        if dp[j] > max_sum:
            max_sum = dp[j]
            end = j
            start = p
    print("Case {}: {} {} {}".format(i+1, max_sum, start+1, end+1))

对于问题2，我们采用DP+单调队列的做法，该内容的具体部分会在后面讲解。

// hdu 1003 求定长的最大子序和，使用DP和单调队列
#include <bits/stdc++.h>
using namespace std;
deque<int> dq;
int s[100010];
int main() {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>s[i];
    for(int i=1;i<=n;i++) s[i]+=s[i-1]; // 前缀和
    int ans=-0x3f3f3f3f;    
    dq.push_back(0);
    for(int i=1;i<=n;i++) {
        while(!dq.empty()&&dq.front()<i-m) dq.pop_front();  // 单调队列维护长度为m的区间
        if(!dq.empty()) ans=max(ans,s[i]);  // 如果队列为空，说明前面的前缀和都是负数，直接取当前前缀和
        else ans=max(ans,s[i]-s[dq.front()]);   // 否则取当前前缀和减去队首的前缀和
        while(!dq.empty()&&s[dq.back()]>=s[i]) dq.pop_back();   // 维护单调队列
        dq.push_back(i);    // 入队
    }
    cout<<ans<<endl;
    return 0;
}

1.2.4 优先队列

优先队列的特征是每次让优先级最高的先出队列，优先队列并不是简单的线性结构，而是用堆（后面会讲到）这种复杂结构来实现。由于代码写起来比较麻烦，C++中一般使用STL编码。

练习题：

求m区间内的最小值 - 洛谷

扫描 - 洛谷

切蛋糕 - 洛谷

好消息，坏消息 - 洛谷

良好的感觉 - 洛谷

[NOIP2017 普及组] 跳房子 - 洛谷

琪露诺 - 洛谷

[SDOI2007] 小组队列 - 洛谷

1.3 栈

栈的特点是“先进后出”。手写栈比手写队列要更简单。

编程中常用的递归就是用栈来实现的。栈需要空间存储，在C++中，如果栈的深度太大，或者进栈的数组太大，那么总数就会超过系统为栈分配的空间，导致爆栈。编码时常用STL stack，为了避免爆栈，要控制栈的大小。

1.3.1 STL stack

Problem - 1062

// 反转字符串，使用STL stack
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    getchar();
    while (n--) {
        stack<char> s;
        char c;
        while ((c = getchar()) != '\n' || c != ' ') {   // 读取字符直到换行或空格
            s.push(c);
        }
        while (!s.empty()) {
            cout << s.top();    // 输出栈顶元素
            s.pop();
        }
        cout << endl;
    }
    return 0;
}

# 翻转字符串，使用List
n = int(input())
l = []
for i in range(n):
    s = list(input())
    for j in range(len(s)):
        l.append(s[j])
    while len(l) > 0:
        print(l.pop(), end='')
    print()

# 翻转字符串
n = int(input())
for i in range(n):
    s = input()
    print(s[::-1])

1.3.2 手写栈

手写代码简单且节省空间。

// 反转字符串，手写栈
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct mystack {
    char s[N];
    int t;
    mystack() {
        t = 0;
    }
    void push(char c) {
        s[t++] = c;
    }
    void pop() {
        t--;
    }
    char top() {
        return s[t - 1];
    }
    bool empty() {
        return t == 0;
    }
};

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        mystack s;
        string str;
        cin >> str;
        for (int j = 0; j < str.length(); j++) {
            s.push(str[j]);
        }
        while (!s.empty()) {
            cout << s.top();
            s.pop();
        }
        cout << endl;
    }
}

# 翻转字符串，手写栈
class MyStack:
    def __init__(self):
        self.stack = []
    def push(self, item):
        self.stack.append(item)
    def pop(self):
        return self.stack.pop()
    def isEmpty(self):
        return self.stack == []

if __name__ == '__main__':
    n = int(input())
    for _ in range(n):
        s = input()
        stack = MyStack()
        for i in s:
            stack.push(i)
        while not stack.isEmpty():
            print(stack.pop(), end='')
        print()

1.3.3 单调栈

单调栈是栈的一种，栈内的元素是单调递增或单调递减的。下面的例题说明单调栈的简单应用。

[USACO09MAR] Look Up S - 洛谷

// 洛谷P2947， 使用STL stack
#include <bits/stdc++.h>
using namespace std;
int h[1000005];
int ans[1000005];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    stack<int> s;
    for (int i = n; i >= 1; i--) {  // 从右往左扫描
        while (!s.empty() && h[s.top()] <= h[i]) s.pop();   // 从栈顶开始，将比当前元素小的元素全部出栈
        if (s.empty())
            ans[i] = 0;
        else
            ans[i] = s.top();
        s.push(i);
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << endl;
    return 0;
}

# 洛谷P2947
n = int(input())
L = [0]
ans = [0]*(n+1)
tmp = [0]
for i in range(n):
    tmp.append(int(input()))
for _ in range(n,0,-1):
    while L and tmp[_] >= tmp[L[-1]]: L.pop()   # 从后往前，如果当前元素大于栈顶元素，则弹出栈顶元素
    ans[_] = L[-1] if L else 0  # 如果栈不为空，则当前元素的答案为栈顶元素，否则为0
    L.append(_) 
for i in range(1,n+1):
    print(ans[i],end='\n')

习题：

【模板】单调栈 - 洛谷

后缀表达式 - 洛谷

表达式括号匹配 - 洛谷

[NOIP2013 普及组] 表达式求值 - 洛谷

表达式的转换 - 洛谷

力扣

力扣

力扣

力扣

1.4 二叉树和哈夫曼树

1.4.1 二叉树的概念

二叉树的每个节点最多有两个节点，分别称为左孩子和右孩子，以它们为根的子树分别称为左子树和右子树。

二叉树的每层节点都以2的倍数递增。如果每层的节点数都是满的，则称它为满二叉树。如果一个n层的满二叉树只在最后一层有缺失，且缺失的编号都在最后，则称为完全二叉树。

满二叉树

完全二叉树

1号节点时二叉树的根，没有父节点。从根到节点u的路径长度定义为u的深度。节点u到它的叶子节点的最大路径长度定义为u的高度。根节点的高度称为树的高度。

二叉树的优势：

1. 二叉树能够进行极高效率的访问。一棵平衡的二叉树，能够提高访问的效率。但是如果二叉树不平衡，甚至在极端情况下退化成一条链，那么访问效率就会大打折扣。
2. 二叉树很适合从整体到局部的、从局部到整体的操作。
3. 基于二叉树的算法容易设计和实现。

二叉树的存储结构：

二叉树可以分为动态存储和静态存储。动态二叉树的数据结构如下：

struct Node
{
    int data;
    Node *left;
    Node *right;
};

在使用动态新建一个Node时，用new申请空间，使用完毕后使用delete释放。

静态存储二叉树的方法如下：

// 二叉树的静态存储
struct Node {
    char data;
    int left, right;
} node[N];

这种方法适用于算法竞赛。

将多叉树转化为二叉树的应用场景并不多见，简单方法就是将第1个孩子作为左孩子，其兄弟节点作为右孩子。这样做的缺点可能会将树退化为1条长链。

# 二叉树
class Node(object):
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild

1.4.2 二叉树的遍历

1. 宽度优先遍历

   有时我们需要按层次将二叉树一层一层的遍历，如图，我们会将该二叉树以E-BG-ADFI-CH的顺序来遍历。

1. 深度优先遍历
   1. 先序遍历：依次访问父节点、左孩子、右孩子。伪代码如下：

先序遍历的结果为：EBADCGFIH。

b. 中序遍历：依次访问左孩子、父节点、右孩子。伪代码如下：

    // 中序遍历
    void inorder(int root) {
        inorder(node[root].left);
        cout << node[root].data;
        inorder(node[root].right);
    }

中序遍历的结果为：ABCDEFGHI。

c. 后序遍历：依次访问左孩子、右孩子、父节点。伪代码如下：

  // 后序遍历
  void postorder(int root) {
      postorder(node[root].left);
      postorder(node[root].right);
      cout << node[root].data;
  }

后序遍历的结果为：ACDBFHIGE。

如果已知某棵二叉树的中序遍历和另一种遍历，就可以把这棵二叉树构造出来。

练习题：

Problem - 1710

1.4.3 哈夫曼树和哈夫曼编码

哈夫曼树是一类带权路径长度最短的最优树，是贪心思想在二叉树中的应用。如何构造一棵哈夫曼树，最简单的方法就是将权值大的节点放在离根节点近的层次上，权值小的节点放在离根节点远的层次上。哈夫曼算法的步骤如下：

1. 把每个权值构造成一刻只有一个节点的树，n个权值构成了n棵树。记为集合F=\{T_1,T_2,...,T_n\}。
2. 在F中选择权值最小的两棵树T_i,T_j，合并成一棵新的二叉树T_x，它的权值等于T_i和T_j的权值之和，左右子树分别为T_i和T_j。
3. 在F中删除T_i和T_j，并把T_x加入F。
4. 重复步骤2，3，知道F中只含有一棵树，这棵树就是哈夫曼树。

哈夫曼编码的方法如下：

信息论和编码第八章笔记 | LittleAO学习小站

下面给出一道例题：

1521 – Entropy

 // poj 1521
 #include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <queue>
 using namespace std;
 int main() {
     priority_queue<int, vector<int>, greater<int> > q;
     string s;
     while(getline(cin, s) && s != "END") {
         sort(s.begin(), s.end());
         int num = 1;
         for(int i = 1; i <= s.length(); i++) {
             if(s[i] == s[i - 1]) num++; // 统计每个字符出现的次数
             else {
                 q.push(num);
                 num = 1;
             }
         }
         int ans = 0;
         if(q.size() == 1) ans = s.length(); // 只有一个字符
         while(q.size() > 1) {
             int a = q.top(); q.pop();   // 每次取出最小的两个数
             int b = q.top(); q.pop();
             q.push(a + b);
             ans += a + b;
         }
         q.pop();
         printf("%d %d %.1f\n", s.length() * 8, ans, (double)s.length() * 8 / ans);
     }
     return 0;
 }

 # poj 1521
 s = ''
 while s != 'END':
     s = input()
     if s == 'END':
         break
     count = []
     for i in set(s):
         count.append(s.count(i))
     count.sort(reverse=True)
     ans = 0
     if len(count) == 1:
         ans = len(count)
     while len(count) > 1:
         a = count.pop()
         b = count.pop()
         ans += a + b
         count.append(a + b)
         count.sort(reverse=True)
     print(len(s) * 8, ans, '%.1f' % (len(s) * 8 / ans))

习题：

Problem - 2527

[NOIP2004 普及组] FBI 树 - 洛谷

[NOIP2001 普及组] 求先序排列 - 洛谷

新二叉树 - 洛谷

遍历问题 - 洛谷

[NOIP2018 普及组] 对称二叉树 - 洛谷

【XR-4】复读 - 洛谷

[NOI2015] 荷马史诗 - 洛谷

1.5 堆

1.5.1 二叉堆的概念

二叉堆是一棵完全二叉树，是用数组实现的二叉树堆，树中的每个节点与数组中存放的元素对应。树的每层，除了最后一层可能不满，其他都是满的。

二叉堆的每个节点，都是以他为父节点的子树的最小值。

用数组A[]储存完全二叉树，节点数量为n，A[1]为根节点，有以下性质：

1. 编号为i>1的节点，其父节点编号为i/2。
2. 如果2i>n，那么节点i没有孩子；如果2i+1>n，那么节点i没有右孩子。
3. 如果节点i有孩子，那么它的左孩子是2i，右孩子是2i+1。

堆的操作有进堆和出堆。

1. 进堆：每次把元素放进对，都调整堆的形状，使根节点保持最小。
2. 出堆：每次取出的堆顶，就是整个堆的最小值；同时调整堆，使新的堆顶最小。

进堆和出堆的时间复杂度均为O(\log_2n)。

1.5.2 二叉堆的操作

堆的操作有两种：上浮和下沉。

上浮：

1. 插入新元素2

2. 将2和7交换

3. 将6和2交换

4. 将3和2交换

5. 完成上浮

下沉：

1. 将7和2交换，弹出2

2. 将7和3交换

3. 将7和6交换

4. 7到达位置，下沉完成

1.5.3 二叉堆的手写代码

【模板】堆 - 洛谷

// 洛谷P3378，手写堆
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int heap[N], len=0;
void push(int x) {
    heap[++len] = x;
    int i = len;
    while (i > 1 && heap[i] < heap[i>>1]) { // i>>1 == i/2
        swap(heap[i], heap[i>>1]);
        i >>= 1; 
    }
}

void pop() {
    heap[1] = heap[len--];
    int i = 1;
    while (i*2 <= len) {
        int j = i*2;
        if (j+1 <= len && heap[j+1] < heap[j]) j++; // 选出左右儿子中较小的
        if (heap[i] <= heap[j]) break;  // 如果父亲比儿子小，就不用交换了
        swap(heap[i], heap[j]); // 否则交换
        i = j;
    }
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int op, x;
        cin >> op;
        if (op == 1) {
            cin >> x;
            push(x);
        } else if (op == 2) {
            cout << heap[1] << endl;
        } else {
            pop();
        }
    }
    return 0;
}

习题：

【模板】堆 - 洛谷

[NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G - 洛谷

中位数 - 洛谷

最小函数值 - 洛谷

[NOIP2016 提高组] 蚯蚓 - 洛谷

[USACO12FEB] Cow Coupons G - 洛谷