今天是个好天气
今天是个好天气
今天是个好天气
我们使用的stack是属于哪个版本的STL？
C++标准库是有多个版本的，才能知道对应的栈和队列的实现原理。下面是三个最为普遍的STL版本：
基本功能
栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。
C++中stack 不是容器
栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。
所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。
我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的低层结构。
deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。
SGI STL中 队列底层实现缺省情况下一样使用deque实现的。
堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。
简单来说大顶堆（堆头是最大元素），小顶堆（堆头是最小元素）。
priority_queue< Node,vector< Node >,cmp > Q;
//定义了一个存放Node型元素，底层是用vector实现，优先级是通过cmp比较获得。
双栈，minst保存了每个数之前的最小值。
用双端队列模拟进出，维护一个单调队列，队首的元素一定是当前窗口中最大的值。
模拟一个小根堆，重写cmp函数，输出前k个元素即可。
或者STL。
返回第k大的元素。
维护一个大顶堆（父节点是最大值），栈中超过k个元素就弹出最小的值，最后返回栈顶即可。
做法2：快速选择。
将非空的链表节点插入小顶堆中，然后不断弹出较小值，插入弹出节点的下一个节点值（非空的话）。
排序所有值，构建新的链表返回。
进阶：分治。
最长，这里指的是连续，难点在于如何更新答案。
不断存放最左侧满足的坐标。
- 遇到左括号，放入坐标值。
- 遇到右括号时，如果当前栈为空，说明连续边界要更换
i + 1- 不为空说明开始匹配子串了，弹出一个坐标，如果不为空说明答案为
i - st.top()，为空说明是一个连续的结束，i - start + 1
用双栈或者单个栈存放数字和字母。当字符为"["时，入栈数字和字符，当字符为"]"，出栈数字和字符。
用
stoi函数完成str转换数字。
想到了优先队列，从小到大存入优先级队列，最后再弹出每个结点
卡了很久的点是结尾的点没有指向nullptr，折磨住了，当然了实际中我们应该使得每个操作合法化，这里可能是答案遍历时出了问题。
也可以直接取出结点，sort然后放入。
二刷应该考虑排序的方法，优化时间复杂度。
通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。
本质是空间换时间，时间复杂度为O(n)。
在使用单调栈的时候首先要明确如下几点：
单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取。
注意一下顺序为 从栈头到栈底的顺序。
stack<int> st;
//此处一般需要给数组最后添加结束标志符，具体下面例题会有详细讲解
for (遍历这个数组)
{
if (栈空 || 栈顶元素大于等于当前比较元素)
{
入栈;
}
else
{
while (栈不为空 && 栈顶元素小于当前元素)
{
栈顶元素出栈;
更新结果;
}
当前数据入栈;
}
}
如果栈中存放的是下表，根据数组下标更新答案
维护一个单调递减的栈，当出现温度大于栈顶元素值时，记录答案。
通过数组下标更新答案。
不过加了一个映射。对nums2单调栈，result[i] 表示 i 这个数字在nums2中第一个比他大的数的下标。
再遍历nums1, result[nums1[i]] == -1说明没有比他大的数，否则就是找到了下标，再把下标对在nums2的值放入，否则就是放入-1。
对比上一题，这题变成了循环数组，一种方法是拼接，这种达到延续前半部分的作用，再对后半部分答案取余。
实际上可以直接利用取余这个操作实现，double的作用。
- 前后缀分解
- 分别计算前缀和后缀的长度
- 每个水柱的高度等于左右边界的较小值，减去当前的高度值
- 双指针
- 单调栈
- 通过栈维护一个高度差。
- 当前高度小于前面高度说明凹陷的部分，入栈
- 当前高度等于前者高度说明平整的，重复了，出栈，入栈新的
- 当前高度大于前者说明形成了一个水柱
- 水柱面积等于 高×宽
- 高度取决于水柱左侧和右侧的最小值以及底部值，比如102，高度应该min(1, 2) - 0 = 1
- 宽度就是当前的位置和水柱左边界的坐标值
右边界计算的非常巧妙啊！比我大的都弹走了，你就是比我小的第一个元素，这就是高度。