下载掌阅APP，畅读海量书库
立即打开
【问题描述】 请设计一个支持以下操作的栈。
（1）CustomStack（int maxSize）：用maxSize初始化对象，其中maxSize是栈中最多能容纳的元素的数量，栈在增长到maxSize之后将不支持push操作。
（2）void push（int x）：如果栈还未增长到maxSize，将 x 添加到栈顶。
（3）int pop（）：弹出栈顶元素，并返回栈顶的值，或栈为空时返回-1。
（4）void increment（int k，int val）：栈底的 k 个元素的值都增加val。如果栈中元素的总数小于 k ，则栈中的所有元素都增加val。
示例：
【限制】 1≤maxSize≤1000，1≤ x ≤1000，1≤ k ≤1000，0≤val≤100。increment、push、pop操作均最多被调用1000次。
图3.2 顺序栈结构
【解题思路】 使用顺序栈实现支持增量操作的栈 。按题目要求，顺序栈中存放栈元素的data数组使用动态数组，栈顶指针为top（初始为-1），另外设置一个表示容量的capacity域（其值为maxSize），如图3.2所示。
（1）push和pop运算算法与基本顺序栈的进/出栈元素算法相同，算法的时间复杂度为 O （1）。
（2）increment（k，val）用于将data数组中下标为0～min（top+1， k ）-1的所有元素增加val，算法的时间复杂度为 O （ k ）。
对应的支持增量操作的类如下。
C++：
提交运行：
Python：
提交运行：
【问题描述】 设计一个支持push、pop、top操作，并且能在常数时间内检索到最小元素的栈，各函数的功能如下。
（1）push（x）：将元素 x 推入栈中。
（2）pop（）：删除栈顶元素。
（3）top（）：获取栈顶元素。
（4）getMin（）：检索栈中的最小元素。
示例：
【限制】 -2 31 ≤val≤2 31 -1，pop、top和getMin操作总是在非空栈上调用，push、pop、top和getMin操作最多被调用3×10 4 次。
【解法1】 使用链栈实现最小栈 。使用带头结点h的单链表作为最小栈，其中每个结点除了存放栈元素（val域）外，还存放当前最小的元素（minval域）。例如，若当前栈中从栈底到栈顶的元素为 a 0 ， a 1 ，…， a i （ i ≥1），则val序列为 a 0 ， a 1 ，…， a i ，minval序列为 b 0 ， b 1 ，…， b i ，其中 b i 恰好为 a 0 ， a 1 ，…， a i 中的最小元素。若栈非空，在进栈元素 a i 时求 b i 的过程如图3.3所示。
（1）push（val）：创建用val域存放val的结点p，若链表h为空或者val小于或等于首结点的minval，则置p-
minval=val，否则置p-
minval为首结点的minval。最后将结点p插入表头作为新的首结点。
（2）pop（）：删除链表h的首结点。
（3）top（）：返回链表h的首结点的val值。
（4）getMin（）：返回链表h的首结点的minval。
可以看出上述4个基本算法的时间复杂度均为 O （1）。
图3.3 非空栈进栈元素 a i 时求 b i 的过程
【解法2】 使用顺序栈实现最小栈 。用两个vector＜int＞容器valst和minst实现最小栈，valst作为val栈（主栈），minst作为min栈（辅助栈），后者作为存放当前最小元素的辅助栈，如图3.4所示，min栈的栈顶元素 y 表示val栈中从栈顶 x 到栈底的最小元素，相同的最小元素也要进入min栈。例如，依次进栈3、5、3、1、3、1后的状态如图3.5所示，从中看出，min栈中元素的个数总是少于或等于val栈中元素的个数。
图3.4 最小栈的结构
图3.5 依次进栈3、5、3、1、3、1后的状态
（1）push（val）：将val进入val栈，若min栈为空或者val小于或等于min栈的栈顶元素，则同时将val进入min栈。
（2）pop（）：从val栈出栈元素e，若min栈的栈顶元素等于e，则同时从min栈出栈元素e。
（3）top（）：返回val栈的栈顶元素。
（4）getMin（）：返回min栈的栈顶元素。
同样，上述4个基本算法的时间复杂度均为 O （1）。
【解法3】 实现辅助空间为 O （1） 的最小栈 。前面两种解法的辅助空间均为2 n （在解法1中每个结点存放两个整数，共2 n 个结点，而解法2中使用两个栈，每个栈的空间为 n ），本解法只使用一个栈st（初始为空），另外设计一个存放当前最小值的变量minval（初始为-1），栈st中仅存放进栈元素与minval的差，这样的辅助空间为 n 。
（1）push（val）：栈st为空时进栈0，置minval=val；否则求出val与minval的差值 d ，将 d 进栈，若 d ＜0，说明val更小，置minval=val（或者说st栈的栈顶元素为 d ，若 d ＜0，说明实际栈顶元素就是minval，否则实际栈顶元素是 d +minval）。
（2）pop（）：出栈栈顶元素 d ，若 d ＜0，说明栈顶元素最小，需要更新minval，即置minval-= d ，否则minval不变。
（3）top（）：设栈顶元素为 d ，若 d ＜0，返回minval，否则返回 d +minval。
（4）getMin（）：栈为空时返回-1，否则返回minval。
例如，st=[]，minval=-1，一个操作示例如下。
（1）push（-2）：将-2进栈，st=[0]，minval=-2。
（2）push（1）：将1进栈，st=[0，3]，minval=-2。
（3）push（-4）：将-4进栈，st=[0，3，-2]，minval=-4。
（4）push（2）：将2进栈，st=[0，3，-2，6]，minval=-4。
（5）top（）：栈顶为6≥0，则实际栈顶元素为6+minval=2。
（6）getMin（）：直接返回minval=-4。
（7）pop（）：从st栈中出栈 d =6，st=[0，3，-2]，由于 d ＞0，说明最小栈元素不变，minval=-4。
（8）top（）：栈顶为-2＜0，说明实际栈顶元素就是minval=-4。
由于测试数据中进栈的元素出现2147483646和-2147483648的情况，在做加减运算时超过int的范围，所以将int改为long long类型。对应的算法如下。
C++：
提交运行：
Python：
提交运行：
【问题描述】 设计一个最大栈数据结构，其既支持栈操作，又支持查找栈中的最大元素。
（1）MaxStack（）：初始化栈对象。
（2）void push（int x）：将元素 x 压入栈中。
（3）int pop（）：移除栈顶元素并返回该元素。
（4）int top（）：返回栈顶元素，无须移除。
（5）int peekMax（）：检索并返回栈中的最大元素，无须移除。
（6）int popMax（）：检索并返回栈中的最大元素，并将其移除。如果有多个最大元素，只要移除最靠近栈顶的那一个。
示例：
【限制】 -10 7 ≤ x ≤10 7 ，最多调用10 4 次push、pop、top、peekMax和popMax，在调用pop、top、peekMax或popMax时栈中至少存在一个元素。
进阶：试着设计这样的解决方案，调用top方法的时间复杂度为 O （1），调用其他方法的时间复杂度为 O （log 2 n ）。
【解法1】 使用两个 vector 向量实现最大栈 。设计两个vector＜int＞向量valst和maxst，其中valst作为val栈（主栈），maxst作为max栈（辅助栈），后者作为存放当前最大元素的辅助栈，两个栈中元素的个数始终相同，若val栈从栈底到栈顶的元素为 a 0 ， a 1 ，…， a i ，max栈从栈底到栈顶的元素为 b 0 ， b 1 ，…， b i ，则 b i 始终为 a 0 到 a i 中的最大元素，如图3.6所示。
例如，依次进栈元素2、1、5、3、9，则valst=[2，1，5，3，9]，而maxst=[2，2，5，5，9]（栈底到栈顶的顺序）。
（1）push（x）：将 x 进入val栈，若max栈为空，则将 x 进入max栈；若max栈不为空，则将 x 和min栈的栈顶元素的最大值进入max栈。
（2）pop（）：从val栈出栈元素e，同时从max栈出栈栈顶元素，返回e。
（3）top（）：返回val栈的栈顶元素。
（4）peekMax（）：返回max栈的栈顶元素。
（5）popMax（）：取max栈的栈顶元素e，从val栈出栈元素直到e，将出栈的元素进入临时栈tmp，同时max栈做同步出栈操作。当val栈遇到元素e时，val栈出栈元素e，max栈做一次出栈操作，再出栈tmp中的所有元素并且调用push将其进栈。最后返回e。
图3.6 最大栈结构（1）
本解法的程序在提交时超时。
【解法2】 使用一个 list 链表和一个 map 映射实现最大栈 。设计一个list＜int＞链表容器作为val栈（每个结点对应一个地址，将其尾部作为栈顶），另外设计一个map＜int，vector＜list＜int＞：：iterator＞＞映射容器mp作为辅助结构，其关键字为进栈的元素值e，值为e对应的结点的地址（按进栈的先后顺序排列）。由于mp使用红黑树结构，默认按关键字递增排列，如图3.7所示。
（1）push（x）：将 x 进入val栈，将该结点的地址添加到mp[ x ]的末尾。
（2）pop（）：从val栈出栈元素e，同时从mp[e]中删除尾元素，最后返回e。
（3）top（）：返回val栈的栈顶元素。
（4）peekMax（）：返回mp中的最大关键字。
（5）popMax（）：获取最大mp中的最大关键字e及其地址it，同时从mp[e]中删除尾元素，再从valst中删除地址为it的结点，最后返回e。
图3.7 最大栈结构（2）
对应的MaxStack类如下。
C++：
提交运行：
说明： 在上述结构中popMax（）算法的时间复杂度为 O （log 2 n ），因此没有超时。
Python：
提交运行：
