分享｜2021秋招算法总结12-栈篇

232. 用栈实现队列、剑指 Offer 09. 用两个栈实现队列和面试题 03.04. 化栈为队：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）。
225. 用队列实现栈：使用队列实现栈的下列操作：push(x) -- 元素 x 入栈；pop() -- 移除栈顶元素；top() -- 获取栈顶元素；empty() -- 返回栈是否为空。
面试题 03.01. 三合一：描述如何只用一个数组来实现三个栈。实现push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum)方法。stackNum表示栈下标，value表示压入的值。

最小/大栈

155. 最小栈、剑指 Offer 30. 包含min函数的栈和面试题 03.02. 栈的最小值：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
716.最大栈：会员题放不了题目，感兴趣的可以看看。

验证栈序列

946.验证栈序列和剑指Offer31.栈的压入、弹出序列：给定 pushed 和 popped 两个序列，每个序列中的值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

栈排序

面试题 03.05. 栈排序：编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。
面试题 03.03. 堆盘子：设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。进阶：实现一个popAt(int index)方法，根据指定的子栈，执行pop操作。

单调栈

仅列举可以用单调栈求解的题目，并不意味着最优解是单调栈，也不意味着其他解法不可行。

84. 柱状图中最大的矩形：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
85. 最大矩形：给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
221. 最大正方形：在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
739. 每日温度：请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
901. 股票价格跨度：编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。
496. 下一个更大元素 I：给你两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
316. 去除重复字母和1081. 不同字符的最小子序列：给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
402. 移掉K位数字：给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
907. 子数组的最小值之和：给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。

结束语

本文为系列完结篇，其实还有一些我笔记中的项目没更新，比如多线程的题，因为没几道题，所以可以直接通过题库查找。更完以后就不常上了，有问题可以留言，万一哪天上来了会统一处理问题的。本系列不保证各位一定能找到工作，但希望大家从中有所收获。祝那些给我点赞的人都能找到满意的工作，也祝那些点踩的人一辈子用不上这些东西吧。