[TOC]

03.01.三合一

用一个数组实现三个栈。

分析：

可以通过将数组的前三分之一分配到第一个栈，第二个三分之一分配到第二个栈，最后的第三个三分之一分配到第三个栈。来模拟数组中的三个栈。实际上某个栈可能比其他的更大，这种平均的分法就不可行了。如果考虑灵活划分，可以移动栈，要保证使用所有可用的容量，把数组看作是循环的。

也可以直接用二维数组来存三个栈。二维数组的每一行代表一个栈，同时使用一个locations记录每个栈待插入的下标。

单调栈

以739.每日温度为例，需要求解的是对于第i天，下一个更高的温度出现在几天后。

对于温度数组t[i] : [1,4,3,5,5,2,3,6]。可以从后往前遍历：

[6]

[6,3]

[6,3,2]

[6,5] 5比2大，弹出2，5比3大，弹出3，5小于6，不再弹出

[6,5] 相同的仍然弹出

[6,5,3]

[6,5,4]

[6,5,4,1]

总结规律：

记录的数据加在最上面，丢掉数据也从最上面开始 —— 后进先出

单调性：记录t[i]之前会把所有<=t[i]的数据丢掉，不可能出现上面大下面小

—— 单调栈

栈顶: st[-1]

把所有小于目标数的元素出栈：

1 2	while st and t >= temperatures[st[-1]]: st.pop()

注意这里栈保存的是温度对应的下标。

出栈后如果栈为空，说明t>=右边数（即气温在这之后都不会升高，初始化完成即可）；如果栈不为空，说明答案为 st[-1] - i （栈顶的数的下标减去i），再将这个元素的下标存到栈顶。

复杂度分析：每个元素最多入栈一次，出栈一次，所以总的循环次数是O(n)。由于栈中不存在相同元素，本题的空间复杂度是O(min(n, U))，U就是数组的最大值减去数组的最小值再加1。

及时去掉无用数据，保证栈中数据有序

如果从左到右遍历：

for i, t in enumerate(temperatures):
    while st and t > temperatures[st[-1]]:
        j = st.pop()
        ans[j] = i - j
    st.append(i)

从左到右遍历的做法更能体现单调栈的特点，一旦t小于等于栈顶，意味着t同时小于等于栈里的任何数。所以t无法更新栈顶，也无法更新栈里任何元素的答案。

练习题: 496.下一个更大元素 I

核心就是单调栈：从右到左遍历，如果大于栈顶元素就出栈，统一入栈。

技巧：建立{元素值:下标} idx = {x:i for i, x in enumerate(nums1)}

42.接雨水

使用了单调栈的方法，通过遍历数组，当遇到一个高度大于等于栈顶元素高度的柱子时，进行雨水的计算，并弹出栈顶元素，直到栈顶元素高度大于当前元素高度或者栈为空。

当判断条件为height[i] >= height[st.peek()]时，只要当前元素的高度不小于栈顶元素的高度，就会进入循环进行处理。
这意味着如果当前元素高度与栈顶元素高度相等，也会触发这个循环。在这种情况下，会弹出栈顶元素，因为相等高度的柱子不能形成蓄水区域，所以不需要保留在栈中。
例如，如果有连续的相同高度的柱子，当遍历到下一个更高的柱子时，这些相同高度的柱子会依次被弹出栈，不会在栈中留下重复的高度。

901.股票价格跨度

运用了 private final Deque<int[]> st = new ArrayDeque<>(); 用于存储股票价格以及对应的日期信息。

st.push(new int[]{-1, Integer.MAX_VALUE}); 在后续的操作中作为边界条件，确保栈在任何时候都至少有一个元素。第一天的日期信息为0。

假设我们有一系列的股票价格传入，依次为：[100, 80, 90, 110, 105, 95]。

首先初始化：
- 双端队列st中有初始元素[-1, Integer.MAX_VALUE]，当前日期curday = -1。
传入第一个价格 100：
- 进入while循环，由于100 < Integer.MAX_VALUE，不满足循环条件。
- 计算跨度：ans = ++curday - st.peek()[0] = 0 - (-1) = 1。
- 将当前日期和价格推入栈：st.push(new int[]{0, 100})。
传入第二个价格 80：
- 进入while循环，80 < 100，不满足循环条件。
- 计算跨度：ans = ++curday - st.peek()[0] = 1 - 0 = 1。
- 将当前日期和价格推入栈：st.push(new int[]{1, 80})。
传入第三个价格 90：
- 进入while循环，90 > 80，满足循环条件，弹出栈顶元素[1, 80]。
- 继续检查，此时栈顶为[0, 100]，90 < 100，不满足循环条件。
- 计算跨度：ans = ++curday - st.peek()[0] = 2 - 0 = 2。
- 将当前日期和价格推入栈：st.push(new int[]{2, 90})。
传入第四个价格 110：
- 进入while循环，110 > 90，满足循环条件，弹出栈顶元素[2, 90]。
- 继续检查，此时栈顶为[0, 100]，110 > 100，满足循环条件，弹出栈顶元素[0, 100]。
- 此时栈为空，不满足循环条件。
- 计算跨度：ans = ++curday - st.peek()[0] = 3 - (-1) = 4。
- 将当前日期和价格推入栈：st.push(new int[]{3, 110})。
传入第五个价格 105：
- 进入while循环，105 < 110，不满足循环条件。
- 计算跨度：ans = ++curday - st.peek()[0] = 4 - 3 = 1。
- 将当前日期和价格推入栈：st.push(new int[]{4, 105})。
传入第六个价格 95：
- 进入while循环，95 < 105，不满足循环条件。
- 计算跨度：ans = ++curday - st.peek()[0] = 5 - 4 = 1。
- 将当前日期和价格推入栈：st.push(new int[]{5, 95})。

通过这个例子可以看到，每次传入一个价格，都会通过检查栈顶元素来确定当前价格的持续区间，从而计算出价格跨度。如果当前价格大于等于栈顶价格，说明栈顶对应的日期在当前价格的持续区间内，所以将其弹出，直到找到一个价格大于当前价格的栈顶元素或者栈为空。

求前k个高频元素

1、统计元素出现频率（使用map进行统计）

2、对频率排序（使用一种容器适配器——优先级队列）

3、找出前k个高频元素

优先级队列

“披着队列外衣”的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，可以看成是队列。

并且优先级队列内部元素自动依照元素的权值排列。

默认情况下priority_queue利用max-heap即大顶堆完成对元素的排序，这个大顶堆是以vector为表现形式的完全二叉树。

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。如果父结点是大于等于左右子节点，就是max-heap；否则为小顶堆。

所以用大顶堆和小顶堆可以直接用优先级队列，底层实现都是一样的，从小到大排就是小顶堆，从大到小排就是大顶堆。

为什么不用快排，使用快排要将map转换为vector的结构，然后对整个数组进行排序，这种场景下，其实只需要k个有序的序列，所以用优先级队列是最优的。

要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。

步骤为：1、根据出现频率构建map

2、构建小顶堆，将所有频率加入到堆中，如果堆的大小大于k，就将元素从堆顶弹出

3、倒叙构建数组

Java语法

//建栈：
Deque<Integer> st = new ArrayDeque<>();
//判断栈非空
!st.isEmpty();
//出栈
st.pop();
//入栈
st.push();
//获取栈顶
st.peek();

哈希表

//建表
Map<Integer, Integer> idx = new HashMap<>(n);
//赋值
idx.put(key, value);
//取值
idx.get(key);

Miraisen

LeetCode栈与队列篇