东风草堂博客

单调栈分为单调递增栈和单调递减栈

1. 单调递增栈即栈内元素保持单调递增的栈
2. 同理单调递减栈即栈内元素保持单调递减的栈
   操作规则（下面都以单调递增栈为例）
3. 如果新的元素比栈顶元素大，就入栈
4. 如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小

柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

1
2
3
4
5
6
7
8
9

stack<int> st;
for(int i = 0; i < nums.size(); i++)
{
	while(!st.empty() && st.top() > nums[i])
	{
		st.pop();
	}
	st.push(nums[i]);
}

什么是递归

周末你带着女朋友去电影院看电影，女朋友问你，咱们现在坐在第几排啊？电影院里面太黑了，看不清，没法数，现在你怎么办？

别忘了你是程序员，这个可难不倒你，递归就开始排上用场了。于是你就问前面一排的人他是第几排，你想只要在他的数字上加一，就知道自己在哪一排了。但是，前面的人也看不清啊，所以他也问他前面的人。就这样一排一排往前问，直到问到第一排的人，说我在第一排，然后再这样一排一排再把数字传回来。直到你前面的人告诉你他在哪一排，于是你就知道答案了。

这就是一个非常标准的递归求解问题的分解过程，去的过程叫“递”，回来的过程叫“归”。基本上，所有的递归问题都可以用递推公式来表示。刚刚这个生活中的例子，我们用递推公式将它表示出来就是这样的：

1

f(n)=f(n-1)+1 其中，f(1)=1

因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作线性排序（Linear sort）。之所以能做到线性的时间复杂度，主要原因是，这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。

桶排序（Bucket sort）

核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。每个桶内部使用快速排序，时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。

桶排序对要排序数据的要求是非常苛刻的。要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。

深入解析网络测速的核心逻辑与实现方案，涵盖chunked数据传输格式、HTTP POST请求机制、基于epoll的高并发网络编程技术，详解客户端与服务端协同测速原理，提供完整的C++代码实现示例。

详细解析读写锁的功能与实现原理，包括读写锁的基本概念、加锁与解锁机制、读写锁的优化策略、读写锁的性能分析等。提供完整的C++代码示例，帮助开发者理解并在实际项目中应用读写锁。

mem

读取文件：/proc/meminfo
MemTotal: 总内存
freeMem: Cached + MemFree + Buffers
程序占用mem：/proc/%d/status
VmRSS: 进程占用内存

cpu

读取文件：/proc/stat
包括：系统cpu、空闲、io等待、irq中断、软中断等。

1

fscanf(file, "%s%lld%lld%lld%lld%lld%lld%lld%lld%lld", temp, &user, &nice, &sys, &idle, &iowait, &irq, &softirq, &steal, &guest);

2G内存在20亿个整数中找出次数最多的数？

kv来描述一个数，一个整数4byte，两个整数8byte，20亿个整数需要16G内存。
数据结构存储：平衡二叉树map、散列表unordered_map。
分治：20亿个整数拆分成若干个范围，分别统计若干个范围中的次数多最大值，汇总若干个范围中的次数最大值，找出次数最大值对应的树。
逆向分析：
2GB = 2 * 2^10 * 2^10 * 2^10 B = 2^31 B，小范围的数字最多 2^31 / 8 = 2^28
有多少个小范围？整数4个字节共32bit，范围为-2^31～2^31，共2^32个整数，2^32/2^28 = 2^4
正向解决：

• 将20亿个数拆分为16个范围
• 将20亿个数依次除以2^28，得到一个0-15的值，放在一个小文件中，另外一种解法：hash分流，相同的key，经过多次hash总是得到相同的值，hash具备随机性，crc16、md5、murmurhash2、siphash、cityhash
• 每个小文件unordered_map[k]++，散列表进行词频统计，如果某一个key出现次数超过10亿，就不必要统计了，这样也可以控制value的范围

40亿个非负整数中算中位数和找出现两次的数

1. 最多使用1GB的内存，找出所有出现了两次的数
   出现了两次，共三种状态：

如果中序遍历为有序的话则为二叉搜索树，为了避免退化为单链表，加入平衡规则后保持平衡则为平衡二叉树，搜索的时间复杂度为O(lgn).
满二叉树、完全二叉树又推出最大堆、最小堆（堆排序、定时器）。平衡二叉树又推出avl、红黑树。
对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

二叉树的递归遍历

前序遍历：根->左->右，1>2>4>5>3>6>7，245这棵树是作为一个整体子树从根节点遍历，这就是递归的思想。
中序遍历：左->根->右，4>2>5>1>6>3>7，每次遍历到子树也是重新左->根->右进行遍历。
后序遍历：左->右->根，4>5>2>6>7>3>1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void PreOrder(TreeNode *root)
{
    if (root == nullptr) return;
    result.push_back(root->val);
    PreOrder(root->left);
    PreOrder(root->right);
}

void InOrder(TreeNode *root)
{
    if (root == nullptr) return;
    InOrder(root->left);
    result.push_back(root->val);
    InOrder(root->right);
}

void PostOrder(TreeNode *root)
{
    if (root == nullptr) return;
    PostOrder(root->left);
    PostOrder(root->right);
    result.push_back(root->val);
}

二叉树的迭代遍历

系统级IO

每个进程都有个umask，通过umask函数来设置的，当进程通过带某个mode参数的open函数来创建一个新文件时，文件的访问权限位被设置为mode & ~umask，也就是umask是程序设定的掩码，哪怕你open时mode为777，最后出来的权限有可能不是777了。

共享文件：

• 每个进程都有它独立的描述符表，它的表项是由进程打开的文件描述符来索引的。每个打开的描述符表项指向文件表中的一个表项。
• 打开文件的集合是由一张文件表来表示的，所有进程共享这张表。文件表表项包括当前的文件位置、引用计数即当前指向该表项的描述符表项数，以及一个指向v-node表中对应表项的指针。引用计数变为0内核才会删除这个文件表项。
• 所有进程共享v-node表。表项包含stat结构中的大部分信息，如st_mode、st_size成员。
  描述符1/4打开不同的文件，有不同的文件表项，以及相对应的v-node:
  
  子进程有父进程描述符的副本，父子进程共享相同的文件表，所以共享相同的文件位置，另外，内核删除相应文件表表项之前，父子进程都必须关闭了它们的文件描述符。
  
  同一个文件open两次，也有不同的文件表项，记录自己的文件位置，但v-node是同一个，这种属于文件共享：
  

IO重定向：