第3章〓栈

 知识图谱




3．1栈概述
3．1．1栈的定义

栈的示意图如图3．1所示，栈中保存一个数据序列［a0，a1，…，an-1］，共有两个端点，栈底的一端(a0端)不动，栈顶的一端(an-1端)是动态的，可以插入(进栈)和删除(出栈)元素。栈元素遵循“先进后出”的原则，即最先进栈的元素最后出栈。注意，不能直接对栈中的元素进行顺序遍历。



图3．1栈的示意图

在算法设计中，栈通常用于存储临时数据。在一般情况下，若先存储的元素后处理，则使用栈数据结构存储这些元素。

n个不同的元素经过一个栈产生不同出栈序列的个数为1n+1Cn2n，这称为第n个Catalan(卡特兰)数。

栈可以使用数组和链表存储结构实现，使用数组实现的栈称为顺序栈，使用链表实现的栈称为链栈。

3．1．2栈的知识点
1． C++中的栈

在C++STL中提供了stack类模板，实现了栈的基本运算，而且在使用时不必考虑栈满上溢出的情况，但不能顺序遍历栈中的元素。其主要的成员函数如下。

 empty()： 判断栈是否为空，当栈中没有元素时返回true，否则返回false。

 size()： 返回栈中当前元素的个数。

 top()： 返回栈顶的元素。

 push(x)： 将元素x进栈。

 pop()： 出栈元素，只是删除栈顶元素，并不返回该元素。

例如，以下代码定义一个整数栈st，依次进栈1、2、3，再依次出栈所有元素，出栈结果是3，2，1。

 C++： 



1stack<int> st;//定义一个整数栈

2st.push(1);								　　//进栈1

3st.push(2);								　　//进栈2

4st.push(3);								　　//进栈3

5while(!st.empty()) {				　　//栈不空时循环

6printf("%d ",st.top());//输出栈顶元素

7st.pop();//出栈栈顶元素

8}



另外，由于C++STL中的vector容器提供了empty()、push_back()、pop_back()和back()等成员函数，也可以将vector容器用作栈。

2．  Python中的栈

在Python中没有直接提供栈，可以将列表作为栈。当定义一个作为栈的st列表后，其主要的栈操作如下。

 st，len(st)==0： 判断栈是否为空，当栈中没有元素时返回True，否则返回False。

 len(st)： 返回栈中当前元素的个数。

 st［-1］： 返回栈顶的元素。

 st．append(x)： 将元素x进栈。

 st．pop()： 出栈元素，只是删除栈顶元素，并不返回该元素。

说明： 在Python中提供了双端队列deque，可以通过限制deque在同一端插入和删除将其作为栈使用。

例如，以下代码用列表st作为一个整数栈，依次进栈1、2、3，再依次出栈所有元素，出栈结果是3，2，1。

 Python： 





1st=［］#将列表作为栈

2st.append(1)#进栈1

3st.append(2)#进栈2

4st.append(3)#进栈3

5while st:#栈不空时循环，或者改为while len(st)>0:

6print(st［-1］,end=' ')#输出栈顶元素

7st.pop()#出栈栈顶元素



3．  单调栈

将一个从栈底元素到栈顶元素有序的栈称为单调栈，如果从栈底元素到栈顶元素是递增的(栈顶元素最大)，称该栈为单调递增栈或者大顶栈，例如［1，2，3］(栈底为1，栈顶为3)就是一个单调递增栈； 如果从栈底元素到栈顶元素是递减的(栈顶元素最小)，称该栈为单调递减栈或者小顶栈，例如［3，2，1］就是一个单调递减栈。

维护单调栈的操作是在向栈中插入元素时可能需要出栈元素，以保持栈中元素的单调性。这里以单调递增栈(大顶栈)为例，假设要插入的元素是x： 

(1) 如果栈顶元素小于(或者等于)x，说明插入x后仍然保持单调性。直接进栈x即可。

(2) 如果栈顶元素大于x，说明插入x后不再满足单调性，需要出栈栈顶元素，直到栈为空或者满足(1)的条件，再将x进栈。

例如，以下代码中定义的单调栈st是一个单调递增栈，执行后st从栈底到栈顶的元素为［1，2，3］。

 C++： 





1vector<int> a={1,5,2,4,3};

2stack<int> st;

3for(int i=0;i<a.size();i++) {//遍历a

4while(!st.empty() && st.top()>a［i］)

5st.pop();　　//将大于a［i］的栈顶元素出栈

6st.push(a［i］);

7}



单调栈的主要用途是寻找下/上一个更大/更小元素，例如给定一个整数数组a，求每个元素的下一个更大元素，可以使用单调递减栈实现。由于在单调栈应用中通常每个元素仅进栈和出栈一次，所以时间复杂度为O(n)。

3．2扩展栈的算法设计
3．2．1LeetCode1381——设计一个支持增量操作的栈★★

【问题描述】请设计一个支持以下操作的栈。

(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。

示例： 



CustomStack customStack=new CustomStack(3); 　　//栈的容量为3，初始为空栈［］

customStack.push(1);　　//栈变为［1］

customStack.push(2);　　//栈变为［1, 2］

customStack.pop(); 　　//返回栈顶值2，栈变为［1］

customStack.push(2);　　//栈变为［1, 2］

customStack.push(3);　　//栈变为［1, 2, 3］

customStack.push(4);//栈是［1, 2, 3］，不能添加其他元素使栈的大小变为4

customStack.increment(5, 100);　　//栈变为［101, 102, 103］

customStack.increment(2, 100);　　//栈变为［201, 202, 103］

customStack.pop();　　//返回栈顶值103，栈变为［201, 202］

customStack.pop(); 　　//返回栈顶值202，栈变为［201］

customStack.pop(); 　　//返回栈顶值201，栈变为［］

customStack.pop(); 　　//栈为空，返回-1



【限制】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++： 




1class CustomStack {

2int *data;//存放栈元素的动态数组







3int capacity;//data数组的容量

4int top;//栈顶指针

5public:

6CustomStack(int maxSize) {　　//构造函数

7data=new int［maxSize］;

8capacity=maxSize;

9top=-1;

10}

11void push(int x) {　　//进栈x

12if(top+1<capacity) {　　//没有出现上溢出时

13top++;data［top］=x;

14}

15}

16int pop() {　　//出栈

17if(top==-1)

18return -1;

19else {

20int e=data［top］; top--;

21return e;

22}

23}

24void increment(int k,int val) {　　//增量操作

25int m=(top+1<=k?top+1:k);

26for(int i=0;i<m;i++)

27data［i］+=val;

28}

29};



提交运行： 



结果：通过;时间：28ms;空间：20.5MB



 Python： 





1class CustomStack:

2def __init__(self, maxSize: int):

3self.data=［None］*maxSize#存放栈元素的动态数组

4self.capacity=maxSize#data数组的容量

5self.top=-1#栈顶指针

6def push(self, x: int) > None:#进栈x

7if self.top+1<self.capacity:#没有出现上溢出时

8self.top=self.top+1

9self.data［self.top］=x

10def pop(self) > int:#出栈

11if self.top==-1:

12return -1

13else:

14e=self.data［self.top］

15self.top=self.top-1

16return e

17def increment(self, k: int, val: int) > None:#增量操作

18m=k

19if self.top+1<=k:m=self.top+1

20for i in range(0,m):

21self.data［i］+=val



提交运行： 



结果：通过;时间：104ms;空间：16MB



3．2．2LeetCode155——最小栈★

【问题描述】设计一个支持 push、pop、top 操作，并且能在常数时间内检索到最小元素的栈，各函数的功能如下。

(1) push(x)： 将元素x推入栈中。

(2) pop()： 删除栈顶元素。

(3) top()： 获取栈顶元素。

(4) getMin()： 检索栈中的最小元素。

示例： 



MinStack minStack=new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin();//返回-3

minStack.pop();

minStack.top();//返回0

minStack.getMin();//返回-2



【限制】-231≤val≤231-1，pop、top 和 getMin 操作总是在非空栈上调用，push、pop、top和getMin操作最多被调用3×104 次。

【看源程序代码请扫描二维码，对应的Word文件为LeetCode155-1．docx】

扫一扫


源程序


【解法1】使用链栈实现最小栈。使用带头结点h的单链表作为最小栈，其中每个结点除了存放栈元素(val域)外，还存放当前最小的元素(minval域)。例如，若当前栈中从栈底到栈顶的元素为a0，a1，…，ai(i≥1)，则val序列为a0，a1，…，ai，minval序列为b0，b1，…，bi，其中bi恰好为a0，a1，…，ai中的最小元素。若栈非空，在进栈元素ai时求bi的过程如图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非空栈进栈元素ai时求bi的过程


【看源程序代码请扫描二维码，对应的Word文件为LeetCode155-2．docx】

扫一扫


源程序


【解法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)的最小栈。前面两种解法的辅助空间均为2n(在解法1中每个结点存放两个整数，共2n个结点，而解法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++： 





1typedef long long LL;

2class MinStack {

3stack<LL> st;

4LL minval=-1;

5public:

6MinStack() {}


7void push(LL val) {

8if(!st.empty()) {//st非空

9LL d=val-minval;

10st.push(d);

11if(d<0) minval=val;

12}

13else {//st为空

14st.push(0);

15minval=val;

16}

17}


18void pop() {

19LL d=st.top(); st.pop();

20if(d<0) minval-=d;

21}


22int top() {

23if(st.top()<0) return minval;

24else return st.top()+minval;

25}


26int getMin() {

27if(st.empty()) return -1;

28else return minval;

29}

30};



提交运行： 



结果：通过;时间：12ms;空间：15.8MB



 Python： 





1class MinStack:

2def __init__(self):

3self.st=［］

4self.minval=-1


5def push(self, val: int) > None:

6if len(self.st)>0:#st非空

7d=val-self.minval

8self.st.append(d)

9if d<0: self.minval=val

10else:#st为空

11self.st.append(0)

12self.minval=val


13def pop(self) > None:

14d=self.st.pop()

15if d<0: self.minval=self.minval-d


16def top(self) > int:

17if self.st［-1］<0:return self.minval

18else:return self.st［-1］+self.minval







19def getMin(self) > int:

20if len(self.st)==0: return -1

21else: return self.minval



提交运行： 



结果：通过;时间：60ms;空间：18.4MB



3．2．3LeetCode716——最大栈★★★

【问题描述】设计一个最大栈数据结构，其既支持栈操作，又支持查找栈中的最大元素。

(1) MaxStack()： 初始化栈对象。

(2) void push(int x)： 将元素x压入栈中。

(3) int pop()： 移除栈顶元素并返回该元素。

(4) int top()： 返回栈顶元素，无须移除。

(5) int peekMax()： 检索并返回栈中的最大元素，无须移除。

(6) int popMax()： 检索并返回栈中的最大元素，并将其移除。如果有多个最大元素，只要移除最靠近栈顶的那一个。

示例： 



MaxStack stk=new MaxStack();

stk.push(5);//［5］，5既是栈顶元素，也是最大元素

stk.push(1);　　//［5, 1］，栈顶元素是1，最大元素是5

stk.push(5);　　//［5, 1, 5］，5既是栈顶元素，也是最大元素

stk.top();　　//返回5，［5, 1, 5］，栈没有改变

stk.popMax();　　//返回5，［5, 1］，栈发生改变，栈顶元素不再是最大元素

stk.top();　　//返回1，［5, 1］，栈没有改变

stk.peekMax();　　//返回5，［5, 1］，栈没有改变

stk.pop();　　//返回1，［5］，此操作后5既是栈顶元素，也是最大元素

stk.top();　　//返回5，［5］，栈没有改变



【限制】-107≤x≤107，最多调用 104次push、pop、top、peekMax 和 popMax，在调用pop、top、peekMax 或 popMax 时栈中至少存在一个元素。

进阶： 试着设计这样的解决方案，调用top方法的时间复杂度为O(1)，调用其他方法的时间复杂度为O(log2n)。

【看源程序代码请扫描二维码，对应的Word文件为LeetCode716．docx】

扫一扫


源程序


【解法1】使用两个vector向量实现最大栈。设计两个vector<int>向量valst和maxst，其中valst作为val栈(主栈)，maxst作为max栈(辅助栈)，后者作为存放当前最大元素的辅助栈，两个栈中元素的个数始终相同，若val栈从栈底到栈顶的元素为a0，a1，…，ai，max栈从栈底到栈顶的元素为b0，b1，…，bi，则bi始终为a0到ai中的最大元素，如图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++： 



1class MaxStack {

2public:

3list<int> valst;//用链表作为val栈

4map<int,vector<list<int>::iterator>> mp;//映射

5MaxStack() {}//构造函数


6void push(int x) {//进栈x

7valst.push_back(x);

8mp［x］.push_back(--valst.end());

9}


10int pop() {//出栈

11int e=valst.back();

12mp［e］.pop_back();

13if(mp［e］.empty()) mp.erase(e);　　//当mp［e］为空时删除该元素

14valst.pop_back();

15return e;

16}



17int top() {//取栈顶元素







18return valst.back();

19}


20int peekMax() {//取栈中的最大元素

21return mp.rbegin()>first;

22}


23int popMax() {//出栈最大元素

24int e=mp.rbegin()>first;

25auto it=mp［e］.back();

26mp［e］.pop_back();

27if(mp［e］.empty()) mp.erase(e);　　//当mp［e］为空时删除该元素

28valst.erase(it);

29return e;

30}

31};



提交运行： 



结果：通过;时间：368ms;空间：145.8MB



说明： 在上述结构中popMax()算法的时间复杂度为O(log2n)，因此没有超时。

 Python： 





1from sortedcontainers import SortedList

2class MaxStack:

3def __init__(self):

4self.idx=0#栈中元素的个数

5self.valst=dict()#作为val栈，元素为(序号，值)

6self.sl=SortedList()#有序序列，元素为(值，序号)，按值递增排列


7def push(self, x: int) > None:#进栈x

8self.valst［self.idx］=x

9self.sl.add((x, self.idx))

10self.idx+=1


11def pop(self) > int:#出栈

12i, x = self.valst.popitem()

13self.sl.remove((x, i))

14return x


15def top(self) > int:#取栈顶元素

16return next(reversed(self.valst.values()))


17def peekMax(self) > int:#取栈中的最大元素

18return self.sl［-1］［0］


19def popMax(self) > int:#出栈最大元素

20x, i = self.sl.pop()

21self.valst.pop(i)

22return x



提交运行： 



结果：通过;时间：572ms;空间：57.7MB



3．3栈应用的算法设计
3．3．1LeetCode1544——整理字符串★★

【问题描述】给定一个由大/小写英文字母组成的字符串s，整理该字符串。一个整理好的字符串中的两个相邻字符s［i］和s［i+1］(0≤i≤s．length-2)要满足以下条件： 

(1) 若s［i］是小写字母，则s［i+1］不可以是相同的大写字母。

(2) 若s［i］是大写字母，则s［i+1］不可以是相同的小写字母。

每次都可以从字符串中选出满足上述条件的两个相邻字符并删除，直到将字符串整理好为止。返回整理好的字符串，题目保证在给出的约束条件下测试样例对应的答案是唯一的。注意，空字符串也属于整理好的字符串，尽管其中没有任何字符。

例如，s="abBAcC"，一种整理过程是"abBAcC"→"aAcC"→"cC"→""，答案为""。

【限制】1≤s．length≤100，s只包含小写英文字母和大写英文字母。

【解题思路】使用栈模拟求解。设计一个字符栈st，用i遍历s，若栈不为空，当s［i］与栈顶字符满足题目中给定的任意一个条件时出栈栈顶字符(相当于删除s［i］和栈顶一对字符)，否则将s［i］进栈。s遍历完毕，将栈中的所有字符按从栈顶到栈底的顺序合并起来得到答案。对应的算法如下。

 C++： 



1class Solution {

2public:

3string makeGood(string s) {

4int n=s.size();

5stack<char> st;

6for(int i=0;i<n;i++) {

7if(!st.empty() && tolower(st.top())==tolower(s［i］) && st.top()!=s［i］)

8st.pop();

9else

10st.push(s［i］);

11}

12string ans="";

13while(!st.empty()) {

14ans=st.top()+ans;

15st.pop();

16}

17return ans;

18}

19};



提交运行： 



结果：通过;时间：4ms;空间：6.9MB



另外，也可以直接用字符串ans模拟栈操作，这样在s遍历完毕，ans中剩下的字符串就是答案。对应的算法如下。

 C++： 



1class Solution {

2public:

3string makeGood(string s) {

4int n=s.size();

5string ans="";

6for(int i=0;i<n;i++) {

7if(!ans.empty() && tolower(ans.back())==tolower(s［i］) && ans.back()!=s［i］)

8ans.pop_back();

9else

10ans.push_back(s［i］);

11}





12return ans;

13}

14};



提交运行： 



结果：通过;时间：0ms;空间：6MB



采用后一种方法对应的Python算法如下。

 Python： 



1class Solution:

2def makeGood(self, s: str) > str:

3ans=［］

4for i in range(0,len(s)):

5if len(ans)>0 and ans［-1］.lower()==s［i］.lower() and ans［-1］!=s［i］:

6ans.pop()

7else:

8ans.append(s［i］)

9return ''.join(ans)



提交运行： 



结果：通过;时间：40ms;空间：15.1MB



3．3．2LeetCode71——简化路径★★

【问题描述】给定一个字符串path，表示指向某一文件或目录的UNIX风格绝对路径(以 '/' 开头)，请将其转换为更加简洁的规范路径并返回得到的规范路径。在UNIX风格的文件系统中，一个点(．)表示当前目录本身； 两个点(．．)表示将目录切换到上一级(指向父目录)； 两者都可以是复杂相对路径的组成部分。任意多个连续的斜线(即'//')都被视为单个斜线 '/'。对于此问题，任何其他格式的点(例如，'．．．')均被视为文件/目录名称。注意，返回的规范路径必须遵循以下格式： 

(1) 始终以斜线'/' 开头。

(2) 两个目录名之间只有一个斜线'/'。

(3) 最后一个目录名(如果存在)不能以 '/' 结尾。

(4) 路径仅包含从根目录到目标文件或目录的路径上的目录(即不含 '．' 或 '．．')。

【看源程序代码请扫描二维码，对应的Word文件为LeetCode71．docx】

扫一扫


源程序


例如，path="/．．/"，答案为"/"，从根目录向上一级是不可行的，因为根目录是可以到达的最高级。path="/a/．/b/．．/．．/c/"，答案为"/c"。

【限制】1≤path．length≤3000，path由英文字母、数字、'．'、'/'或'_'组成，并且是一个有效的UNIX风格绝对路径。

【解题思路】用栈模拟进入下一级目录(前进)和上一级目录(回退)操作。先将path按'/'分隔符提取出对应的字符串序列，例如，path="/a/．/b/．．/．．/c/"时对应的字符串序列为""，"a"，"．"，"b"，"．．"，"．．"，"c"。然后定义一个字符串栈st，用word遍历所有字符串，若word="．"，则跳过； 若word="．．"，则回退，即出栈一次； 若word为其他非空字符串，则将其进栈。遍历前面字符串序列的结果如图3．8所示。

遍历完毕将栈中的所有字符串按从栈底到栈顶的顺序加上"＼"并连接起来构成ans，这里ans="/c"，最后返回ans。



图3．8遍历字符串序列的结果



3．3．3LeetCode1441——用栈操作构建数组★

【问题描述】给定一个目标数组 target 和一个整数 n，每次迭代，需要从 list={1，2，3，…，n}中依次读取一个数字，请使用下述操作构建目标数组target。

(1) Push： 从 list 中读取一个新元素，并将其推入数组中。

(2) Pop： 删除数组中的最后一个元素。

如果目标数组构建完成，停止读取更多元素。题目数据保证目标数组严格递增，并且只包含1~n的数字。请返回构建目标数组所用的操作序列。题目数据保证答案是唯一的。

例如，输入target=［1，3］，n=3，输出为［"Push"，"Push"，"Pop"，"Push"］。读取1并自动推入数组>［1］，读取2并自动推入数组，然后删除它>［1］，读取3并自动推入数组>［1，3］。

【限制】1≤target．length≤100，1≤target［i］≤100，1≤n≤100。target 是严格递增的。

【解题思路】使用栈实现两个序列的简单匹配。用j从0开始遍历target，用i从1到n循环： 先将i进栈(每个i总是要进栈的，这里并没有真正设计一个栈，栈操作是通过"Push"和"Pop"表示的，存放在结果数组ans中)，若当前进栈的元素i不等于target［j］，则将i出栈，否则j加1继续比较，如图3．9所示。若target中的所有元素处理完毕，退出循环。最后返回ans。



图3．9栈操作过程


对应的算法如下。

 C++： 



1class Solution {

2public:

3vector<string> buildArray(vector<int>& target,int n) {

4vector<string> ans;

5int j=0;//遍历target数组

6for(int i=1;i<=n;i++) {

7ans.push_back("Push");//i进栈

8if(i!=target［j］)//target数组的当前元素不等于i

9ans.push_back("Pop");//出栈i

10else//target数组的当前元素等于i

11j++;

12if(j==target.size())//target数组遍历完后退出循环

13break;





14}

15return ans; 

16}

17};



提交运行： 



结果：通过;时间：4ms;空间：7.6MB



 Python： 



1class Solution:

2def buildArray(self, target: List［int］, n: int) > List［str］:

3ans=［］

4j=0#遍历target数组

5for i in range(1,n+1):

6ans.append("Push")#i进栈

7if i!=target［j］:#target数组的当前元素不等于i

8ans.append("Pop")#出栈i

9else:#target数组的当前元素等于i

10j=j+1

11if j==len(target):#target数组遍历完后退出循环

12break;

13return ans



提交运行： 



结果：通过;时间：36ms;空间：14.9MB



3．3．4LeetCode946——验证栈序列★★

【问题描述】给定 pushed 和 popped 两个序列，每个序列中的值都不重复，只有当它们可能是在最初空栈上进行的推入push和弹出pop操作序列的结果时返回 true，否则返回 false。

例如，pushed=［1，2，3，4，5］，popped=［4，5，3，2，1］，输出为true； pushed=［1，2，3，4，5］，popped=［4，3，5，1，2］，输出为false。

【限制】0≤pushed．length=popped．length≤1000，0≤pushed［i］，popped［i］<1000，并且pushed 是 popped 的一个排列。

【解题思路】使用栈实现两个序列的简单匹配。先考虑这样的情况，假设a和b序列中均含n(n≥1)个整数，都是1~n的某个排列，现在要判断b是否为以a作为输入序列的一个合法的出栈序列，即a序列经过一个栈是否得到了b的出栈序列。求解思路是先建立一个st，用j遍历b序列(初始为0)，i从0开始遍历a序列： 

(1) 将a［i］进栈。

(2) 栈不为空并且栈顶元素与b［j］相同时循环： 出栈一个元素同时执行j++。

在上述过程结束后，如果栈为空，返回true表示b序列是a序列的出栈序列，否则返回false表示b序列不是a序列的出栈序列。

例如a={1，2，3，4，5}，b={3，2，4，5，1}，由a产生b的过程如图3．10所示，所以返回true。对应的算法如下。

 C++： 





1class Solution {

2public:

3bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {

4stack<int> st;

5int j=0;

6for(int i=0;i<pushed.size();i++) {//输入序列没有遍历完

7st.push(pushed［i］);//元素pushed［i］进栈

8while(!st.empty() && st.top()==popped［j］) {

9st.pop();//popped［j］与栈顶匹配时出栈

10j++;

11}

12}

13return st.empty();//栈为空返回True，否则返回False

14}

15};





图3．10由a={1，2，3，4，5}产生b={3，2，4，5，1}的过程


提交运行： 



结果：通过;时间：4ms;空间：14.9MB



 Python： 





1class Solution:

2def validateStackSequences(self, pushed: List［int］, popped: List［int］) > bool:

3st=［］

4 j=0

5for i in range(0,len(pushed)):#输入序列没有遍历完

6st.append(pushed［i］)#pushed［i］进栈

7while len(st)>0 and st［-1］==popped［j］:

8st.pop()#popped［j］与栈顶匹配时出栈

9j=j+1

10return len(st)==0#栈为空返回True，否则返回False



提交运行： 



结果：通过;时间：28ms;空间：15.1MB



3．3．5LeetCode20——有效的括号★

【问题描述】给定一个只包含 '('、')'、'{'、'}'、'［'、'］' 的字符串s，判断字符串是否有效。有效字符串需满足： 左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合，每个右括号都有一个对应的相同类型的左括号。

例如，s="()［］{}"时答案为true，s="(］"时答案为false。

【限制】1≤s．length≤104，s仅由'('、')'、［'、'］'、{'、'}'组成。



图3．11括号的匹配

【看源程序代码请扫描二维码，对应的Word文件为LeetCode20．docx】

扫一扫


源程序


【解题思路】使用栈实现括号的最近匹配。字符串s中各种括号的匹配如图3．11所示，也就是说每个右括号总是与前面最接近的尚未匹配的左括号进行匹配，即满足最近匹配原则，所以用一个栈求解。



先建立仅存放左括号的栈st，i从0开始遍历s： 

(1) s［i］为任一左括号时将其进栈。

(2) 若s［i］=')'，如果栈st为空，说明该')'无法匹配，返回false； 若栈顶不是'('，同样说明该')'无法匹配，返回false； 否则出栈'('继续判断。

(3) 若s［i］='］'，如果栈st为空，说明该'］'无法匹配，返回false； 若栈顶不是'［'，同样说明该'］'无法匹配，返回false； 否则出栈'［'继续判断。

(4) 若s［i］='}'，如果栈st为空，说明该'}'无法匹配，返回false； 若栈顶不是'{'，同样说明该'}'无法匹配，返回false； 否则出栈'{'继续判断。

s遍历完毕，若栈为空，说明s是有效的，返回true； 否则说明s是无效的，返回false。



3．3．6LeetCode1249——删除无效的括号★★

【问题描述】给定一个由'('、')'和小写字母组成的字符串s，从该字符串中删除最少数目的'('或者')'(可以删除任意位置的括号)，使得剩下的括号字符串有效，请返回任意一个有效括号字符串。有效括号字符串应当符合以下任意一条要求： 

(1) 空字符串或者只包含小写字母的字符串。

(2) 可以被写成AB(A 连接 B)的字符串，其中 A 和 B 都是有效括号字符串。

(3) 可以被写成(A) 的字符串，其中 A 是一个有效括号字符串。

例如，s="lee(t(c)o)de)"，答案为"lee(t(c)o)de"、"lee(t(co)de)"或者"lee(t(c)ode)"； s="))(("，答案为""。

【限制】1≤s．length≤105，s［i］可能是'('、')'或者英文小写字母。

【解题思路】使用栈实现括号的最近匹配。定义一个栈st(保存所有无效的括号)，循环处理s中的每个字符ch=s［i］： 如果ch为'('，将其序号i进栈； 如果ch为右括号')'，且栈顶为'('，出栈栈顶元素(说明这一对括号是匹配的)； 否则将其序号i进栈，其他字符直接跳过。最后从栈顶到栈底处理栈中的所有序号，依次删除其相应的无效括号。例如，s="lee(t(c)o)de)"，通过栈st找到两对匹配的括号，遍历完毕栈中只含有最后一个右括号的下标，即st=［12］，删除该无效括号后s="lee(t(c)o)de"，如图3．12所示。



图3．12删除无效的括号


对应的算法如下。

 C++： 



1class Solution {

2public:

3string minRemoveToMakeValid(string s) {

4stack<int> st;





5for(int i=0;i<s.size();i++) {

6char ch=s［i］;

7if(ch=='(') st.push(i);

8else if(ch==')') {

9if(!st.empty() && s［st.top()］=='(') st.pop();

10else st.push(i);//将未匹配的')'的位置进栈

11}

12}

13while(!st.empty()) {

14int i=st.top(); st.pop();

15s.erase(s.begin()+i);

16}

17return s;

18}

19};



提交运行： 



结果：通过;时间：32ms;空间：10.6MB



 Python： 



1class Solution:

2def minRemoveToMakeValid(self, s: str) > str:

3st=［］

4for i in range(0,len(s)):

5ch=s［i］

6if ch=='(':st.append(i)

7elif ch==')':

8if len(st)>0 and s［st［-1］］=='(': st.pop()

9else: st.append(i)

10ns=list(s)

11while len(st)>0:

12i=st［-1］; st.pop()

13ns.pop(i)

14return ''.join(ns)



提交运行： 



结果：通过;时间：260ms;空间：16.6MB



3．3．7LeetCode32——最长的有效括号子串的长度★★★

【问题描述】给定一个只包含'('和')'的字符串s，找出最长有效(格式正确且连续)括号子串的长度。

例如，s=")()())"，答案为4，其中最长有效括号子串是"()()"； s=""时答案为0。

【限制】0≤s．length≤3×104，s［i］为'('或者')'。

【解题思路】使用栈实现括号的最近匹配。使用一个栈在遍历字符串s的过程中判断到目前为止扫描的子串的有效性，同时得到最长有效括号子串的长度。具体做法是始终保持栈底元素为当前最后一个没有被匹配的右括号的下标，这样主要是考虑了边界条件的处理，栈中的其他元素维护左括号的下标，用i从0开始遍历字符串s： 

(1) 若s［i］='('，将下标i进栈。

(2) 若s［i］=')'，出栈栈顶元素，表示匹配了当前的右括号。如果栈为空，说明当前的右括号为没有被匹配的右括号，将其下标进栈，以更新最后一个没有被匹配的右括号的下标； 如果栈不为空，当前右括号的下标减去栈顶元素即为以该右括号为结尾的最长有效括号子串的长度，在所有这样的长度中求最大值ans，最后返回ans即可。需要注意的是，如果一开始栈为空，当第一个字符为'('时会将其下标进栈，这样栈底就不满足是最后一个没有被匹配的右括号的下标，为了保持统一，初始时往栈中进栈一个值-1。

例如，s=")()())"，ans=0，st=［-1］，遍历s如下：  

(1) s［0］=')'，出栈-1，栈为空，说明该')'没有被匹配，将其下标0进栈，st=［0］。

(2) s［1］='('，将其下标1进栈，st=［0，1］。

(3) s［2］=')'，出栈1，此时栈st=［0］，栈不为空，说明找到匹配的子串"()"，其长度为2-st．top()=2-0=2，ans=max(ans，2)=2。

(4) s［3］='('，将其下标3进栈，st=［0，3］。

(5) s［4］=')'，出栈3，此时栈st=［0］，栈不为空，说明找到匹配的子串"()()"，其长度为4-st．top()=4-0=4，ans=max(ans，4)=4。

(6) s［5］=')'，出栈0，栈为空，说明该')'没有被匹配，将其下标5进栈，st=［5］。

s遍历完毕，最后答案为ans=4。对应的算法如下。

 C++： 



1class Solution {

2public:

3int longestValidParentheses(string s) {

4int n=s.size();

5if(n==0) return 0;

6int ans=0;

7stack<int> st;

8st.push(-1);

9for(int i=0;i<n;i++) {

10if(s［i］=='(') st.push(i);

11else {

12st.pop();

13if(st.empty()) st.push(i);//更新栈底为最后未匹配的右括号的下标

14else ans=max(ans,i-st.top());//找到有效括号子串, 长度=i-st.top()

15}

16}

17return ans;

18}

19};



提交运行： 



结果：通过;时间：0ms;空间：7.2MB



 Python： 



1class Solution:

2def longestValidParentheses(self, s: str) > int:

3n=len(s)

4if n==0:return 0

5ans=0

6st=［］

7st.append(-1)

8for i in range(0,n):

9if s［i］=='(': st.append(i)

10else:

11st.pop()

12if len(st)==0:st.append(i)

13else: ans=max(ans,i-st［-1］)

14return ans



提交运行： 



结果：通过;时间：44ms;空间：15.7MB



3．4单调栈应用的算法设计
3．4．1LeetCode503——下一个更大元素Ⅱ★★

【问题描述】给定一个循环数组nums(nums［nums．length-1］的下一个元素是nums［0］)，返回nums中每个元素的下一个更大元素。数字x的下一个更大元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着应该循环地搜索它的下一个更大的数。如果不存在下一个更大元素，则输出-1。

例如，nums=［1，2，3，4，3］，对应的答案为ans=［2，3，4，-1，4］，即nums［0］=1的下一个循环更大的数是2，nums［1］=2的下一个循环更大的数是3，以此类推。

【限制】1≤nums．length≤104，-109≤nums［i］≤109。

【解题思路】使用单调栈求下一个更大元素。先不考虑循环，对于nums［i］，仅求nums［i+1．．n-1］中的下一个更大元素。使用单调递减栈保存进栈元素的下标，设计ans数组存放答案，即ans［i］表示nums［i］的下一个循环更大的数。用i从0开始遍历nums数组，按下标对应的数组元素进行比较，若栈顶为j并且nums［j］<nums［i］，则nums［j］的下一个更大元素即为nums［i］(因为如果有更靠前的更大元素，那么这些下标将被提前出栈)，其操作如图3．13所示。



图3．13找nums［j］的下一个更大元素的操作


例如，nums=［1，2，3，4，3］，小顶单调栈st=［］，求解过程如下： 

(1) nums［0］=1，栈为空，直接将序号0进栈，st=［0］。

(2) nums［1］=2，栈顶元素nums［0］=1<2，说明当前元素2是栈顶元素的下一个循环更大的数，则出栈栈顶元素0，置ans［0］=nums［1］=2，再将序号1进栈，st=［1］。

(3) nums［2］=3，栈顶元素nums［1］=2<3，说明当前元素3是栈顶元素的下一个循环更大的数，则出栈栈顶元素1，置ans［1］=nums［2］=3，再将序号2进栈，st=［2］。

(4) nums［3］=4，栈顶元素nums［2］=3<4，说明当前元素4是栈顶元素的下一个循环更大的数，则出栈栈顶元素2，置ans［2］=nums［3］=4，再将序号2进栈，st=［3］。

(5) nums［4］=3，栈顶元素nums［3］=4<3不成立，将nums［3］进栈，st=［3，4］。

此时遍历完毕，栈中的元素都没有下一个更大元素，即ans［3］=ans［4］=-1，最后得到ans=［2，3，4，-1，-1］。

本题求下一个循环更大的数，所以按上述过程遍历nums一次是不够的，还需要回过来考虑前面的元素，一种朴素的思路是把这个循环数组拉直，即复制该数组的前n-1个元素拼接在原数组的后面，这样就可以将这个新数组当作普通数组来处理。在本题中实际上不需要显性地将该循环数组拉直，只需要在处理时对下标取模即可。对应的算法如下。

 C++： 



1class Solution {

2public:

3vector<int> nextGreaterElements(vector<int>& nums) {

4int n=nums.size();

5vector<int> ans(n,-1);

6stack<int> st;//单调递减栈

7for(int i=0;i<2*n-1;i++) {

8while(!st.empty() && nums［st.top()］<nums［i%n］) {

9ans［st.top()］=nums［i%n］;//栈顶元素的下一个更大元素为nums［i%n］

10st.pop();

11}

12st.push(i%n);

13}

14return ans;

15}

16};



提交运行： 



结果：通过;时间：36ms;空间：23.2MB



 Python： 



1class Solution:

2def nextGreaterElements(self, nums: List［int］) > List［int］:

3n=len(nums)

4ans,st=［-1］*n,［］

5for i in range(0,2*n-1):

6while len(st) and nums［st［-1］］<nums［i%n］:

7ans［st［-1］］=nums［i % n］

8st.pop()

9st.append(i % n);

10return ans



提交运行： 



结果：通过;时间：104ms;空间：16.5MB



3．4．2LeetCode496——下一个更大元素Ⅰ★

【问题描述】nums1中数字x的下一个更大元素是指x在 nums2中对应位置右侧的第一个比 x大的元素。给定两个没有重复元素的数组nums1和nums2，下标从0开始计数，其中nums1是nums2的子集。对于每个0≤i<nums1．length，找出满足nums1［i］=nums2［j］的下标j，并且在nums2中确定nums2［j］的下一个更大元素，如果不存在下一个更大元素，那么本次查询的答案是-1。返回一个长度为nums1．length的数组ans作为答案，满足ans［i］是如上所述的下一个更大元素。

例如，nums1=［4，1，2］，nums2=［1，3，4，2］。求nums1中每个值的下一个更大元素的过程如下： 

(1) nums1［0］=4，对于nums2［2］=4，无法在nums2中找到下一个更大元素，答案是-1。

(2) nums1［1］=1，对于nums2［0］=1，在nums2中找到下一个更大元素为3，答案是3。

(3) nums1［2］=2，对于nums2［3］=2，无法在nums2中找到下一个更大元素，答案是-1。

最后答案为ans=［-1，3，-1］。

【限制】1≤nums1．length≤nums2．length≤1000，0≤nums1［i］，nums2［i］≤104，nums1和nums2中的所有整数互不相同，nums1 中的所有整数同样出现在 nums2 中。

【解题思路】使用单调栈求下一个更大元素。由于nums2中的所有元素都不相同，为此设置一个哈希表hmap，hmap［x］表示nums2中元素x的下一个更大元素。采用3．4．1节的思路，使用单调递减栈（小顶栈）求出hmap，再遍历nums1数组(nums1是nums2的子集)。对于nums1［i］，若hmap中存在nums1［i］为关键字的元素，说明nums1［i］在nums2中的下一个更大元素为hmap［nums1［i］］，置ans［i］=hmap［nums1［i］］； 否则说明nums1［i］在nums2中没有下一个更大元素，置ans［i］=-1。最后返回ans即可。对应的算法如下。

 C++： 



1class Solution {

2public:

3vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {

4unordered_map<int,int> hmap;//哈希表

5int m=nums1.size(),n=nums2.size();

6stack<int> st;//小顶栈

7for(int i=0;i<n;i++) {

8while(!st.empty() && st.top()<nums2［i］) {

9hmap［st.top()］=nums2［i］; st.pop();//小于nums［i］的元素出栈

10}

11st.push(nums2［i］);

12}

13vector<int> ans(m,-1);//初始化所有元素为-1

14for(int i=0;i<m;i++) {

15if(hmap.find(nums1［i］)==hmap.end()) continue;

16ans［i］=hmap［nums1［i］］;





17}

18return ans;

19}

20};



提交运行： 



结果：通过;时间：4ms;空间：8.5MB



 Python： 





1class Solution:

2def nextGreaterElement(self, nums1: List［int］, nums2: List［int］) > List［int］:

3dict={}

4m,n=len(nums1),len(nums2)

5st=［］#小顶栈

6for i in range(0,n):

7while len(st)>0 and st［-1］<nums2［i］:

8dict［st［-1］］=nums2［i］

9st.pop()#将小于nums［i］的元素出栈

10st.append(nums2［i］)

11ans=［-1］*m

12for i in range(0,m):

13if dict.get(nums1［i］)==None: continue;

14ans［i］=dict.get(nums1［i］)

15return ans



提交运行： 



结果：通过;时间：36ms;空间：15.1MB



3．4．3LeetCode739——每日温度★★

【问题描述】给定一个整数数组a，表示每天的温度，返回一个数组ans，其中ans［i］指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，a=［73，74，75，71，69，72，76，73］，对应的答案为ans=［1，1，4，2，1，1，0，0］。

【限制】1≤a．length≤105，30≤a［i］≤100。

【解题思路】使用单调栈求下一个更大元素。本题与3．4．2节类似，仅将求当前元素的下一个更大元素改为求当前元素与其下一个更大元素之间的距离。同样使用单调递减栈（小顶栈）求解，对应的算法如下。

 C++： 





1class Solution {

2public:

3vector<int> dailyA(vector<int>& a) {

4int n=a.size();

5vector<int> ans(n,0);

6stack<int> st;//小顶栈

7for(int i=0;i<n;i++) {

8while(!st.empty() && a［st.top()］<a［i］) {

9int prei=st.top();

10ans［prei］=i-prei;

11st.pop();

12}





13st.push(i);

14}

15return ans;

16}

17};



提交运行： 



结果：通过;时间：144ms;空间：100.5MB



 Python： 



1class Solution:

2def dailyA(self, a: List［int］) > List［int］:

3n=len(a)

4ans=［0］*n

5st=［］

6for i in range(0,n):

7while st and a［st［-1］］<a［i］:

8prei=st［-1］

9ans［prei］=i-prei

10st.pop()

11st.append(i)

12return ans



提交运行： 



结果：通过;时间：216ms;空间：23.1MB



3．4．4LeetCode316——去除重复字母★★

【问题描述】给定一个字符串s，请去除字符串中重复的字母，使得每个字母只出现一次，并且保证返回结果的字典序最小(要求不能打乱其他字符的相对位置)。

例如，s="cbacdcbc"，答案为"acdb"。

【限制】1≤s．length≤104，s由小写英文字母组成。

【解题思路】使用单调栈求下一个更小元素。所谓字典序最小，就是去除重复字母，并且使字典序小的字母尽可能往前，字典序大的字母尽可能往后，简单地说就是尽可能保证结果字符串中全部或者局部子串是按字典序递增的。使用单调递增栈（大顶栈）求解，先遍历字符串s，用cnt数组记录每个字母出现的次数。再从前往后遍历，对于当前字母c： 

(1) 如果 c在栈中，说明 c 已经找到了最佳位置，只需要将其计数减1。

(2) 否则将栈顶所有字典序更大(st．top()>c，递减)且后面还有的字母(cnt［st．top()］≥1)的栈顶字母出栈(对于字典序更大但后面不出现的字母则不必弹出)。再将c进栈，同时将其计数减1。

为了快速判断一个字母是否在栈中，设计一个visited数组，若visited［c］=1，表示字母c在栈中； 若visited［c］=0，表示字母c不在栈中。

例如，s="cbacdcbc"，求出每个字母出现的次数为cnt［'a'］=1，cnt［'b'］=2，cnt［'c'］=4，cnt［'d'］=1，栈st=［］，用c遍历s： 

(1) c='c'，栈为空，'c'进栈(visited［'c'］=1)，st=［'c'］，其计数减1，即cnt［'c'］=3。

(2) c='b'，'b'不在栈中且栈顶字母满足'c'>'b'(递减)，出栈'c'(visited［'c'］=0)，st=［］，'b'进栈(visited［'b'］=1)，st=［'b'］，其计数减1，即cnt［'b'］=1。

(3) c='a'，'a'不在栈中且栈顶字母满足'b'>'a'(递减)，出栈'b'(visited［'b'］=0)，st=［］，'a'进栈(visited［'a'］=1)，st=［'a'］，其计数减1，即cnt［'a'］=0。

(4) c='c'，'c'不在栈中且栈顶字母'a'<'c'(递增)，将'c'进栈(visited［'c'］=1)，st=［'a'，'c'］，其计数减1，即cnt［'c'］=2。


扫一扫


源程序


【看源程序代码请扫描二维码，对应的Word文件为LeetCode316．docx】
(5) c='d'，'d'不在栈中且栈顶字母'c'<'d'(递增)，将'd'进栈(visited［'d'］=1)，st=［'a'，'c'，'d'］，其计数减1，即cnt［'d'］=0。

(6) c='c'，'c'在栈中，其计数减1，即cnt［'c'］=1。

(7) c='b'，'b'不在栈中，尽管栈顶字母'd'>'b'(递减)，但cnt［'d'］=0，所以'd'不出栈，将'b'进栈(visited［'b'］=1)，st=［'a'，'c'，'d'，'b'］，其计数减1，即cnt［'b'］=0。

(8) c='c'，'c'在栈中，其计数减1，即cnt［'c'］=0。

遍历完毕，最后将st栈中从栈底到栈顶的所有字母连接起来得到答案，这里为ans="acdb"。

3．4．5LeetCode84——柱状图中最大的矩形★★★

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

例如，对于如图3．14所示的柱状图，每个柱子的宽度为1，6个柱子的高度为［2，1，5，6，2，3］，其中最大矩形面积为 10 个单位。

【解题思路】用单调递增栈找多个元素的共同右边界。先用穷举法求解，用k遍历a，对于以a［k］为高度作为矩形的高度，向左找到第一个小于a［k］的高度a［i］，称柱子i为左边界，向右找到第一个小于a［k］的高度a［j］，称柱子j为右边界，a［k］对应的最大矩形为a［i+1．．j-1］(不含柱子i和柱子j)，共包含j-i-1个柱子，宽度length=j-i-1，其面积为a［k］×(j-i-1)，通过比较将最大面积存放到ans中，a遍历完毕返回ans即可。

例如，a=［1，4，3，6，4，2，5］，k=2时对应的矩形及其面积如图3．15所示。




图3．14一个柱状图及其最大矩形




图3．15以a［2］为高度的矩形



对应的穷举算法如下。

 C++： 



1class Solution {

2public:

3int largestRectangleArea(vector<int>&a) {

4int n=a.size();

5int ans=0;

6for(int k=0;k<n;k++) {





7int length=1;

8int i=k;

9while(--i>=0 && a［i］>=a［k］) length++;

10int j=k;

11while(++j<n && a［j］>=a［k］) length++;

12int area=length*a［k］;

13ans=max(ans,area);

14}

15return ans;

16}

17};



提交运行： 



结果：超时(98个测试用例中通过了86个)



上述算法的时间复杂度为O(n2)，出现超时的情况。可以使用单调递增栈（大顶栈）提高性能，为了设置高度数组a的左、右边界，在a中前后添加一个0(0表示最小柱高度)。用j从0开始遍历a，用栈st维护一个柱子高度递增序列： 

(1) 若栈为空，则直接将j进栈。

(2) 若栈不为空且栈顶柱子k的高度a［k］小于或等于a［j］，则直接将j进栈。

(3) 若栈不为空且栈顶柱子k的高度a［k］大于a［j］，则柱子k找到了右边第一个小于其高度的柱子j(这里大顶单调栈是为了找栈顶柱子的下一个高度更小的柱子)，也就是说柱子k的右边界是柱子j。将柱子k出栈，新栈顶柱子st．top()的高度肯定小于柱子k的高度，所以将柱子st．top()作为柱子k的左边界，对应矩形的宽度length=j-st．top()-1，其面积=a［k］×length。然后对新栈顶柱子做同样的运算，直到不满足条件为止。再将j进栈。

例如，a=［1，2，3，4，2］，前后添加0后a=［0，1，2，3，4，2，0］，如图3．16所示，用“x［y］”表示a［x］=y，即柱子x的高度为y。ans=0，求面积的部分过程如下。



图3．16a=［0，1，2，3，4，2，0］

依次将0［0］、1［1］、2［2］、3［3］和4［4］进栈，st={0［0］，1［1］，2［2］，3［3］，4［4］}。当遍历到a［5］=2时(j=5)： 

(1) 栈顶4［4］的高度大于a［5］，柱子5作为柱子4的右边界，出栈4［4］，即k=4，st={0［0］，1［1］，2［2］，3［3］}，新栈顶为3［3］，将柱子3作为柱子4的左边界，求出area=a［k］×(j-st．top()-1)=4×1=4ans=4。

(2) 新栈顶3［3］的高度大于a［5］，柱子5作为柱子3的右边界(其中柱子4的高度一定大于柱子3的高度，见图3．15)，出栈3［3］，即k=3，st={0［0］，1［1］，2［2］}，新栈顶为2［2］，将柱子2作为柱子3的左边界，求出area=a［k］×(j-st．top()-1)=3×2=6ans=6。

(3) 新栈顶2［2］的高度大于a［5］不成立，将j=5进栈。

从中看出通过单调栈可以一次求出多个柱子的右边界，同时又可以快速求出这些柱子的左边界。尽管在算法中使用了两重循环，实际上每个柱子最多进栈、出栈一次，所以算法的时间复杂度为O(n)。对应的算法如下。

 C++： 





1class Solution {

2public:

3int largestRectangleArea(vector<int>&a) {

4a.insert(a.begin(),0);

5a.push_back(0);

6int n=a.size();

7stack<int> st;//大顶栈

8int ans=0;//存放最大矩形面积，初始为0

9for(int j=0;j<n;j++) {//遍历a

10while(!st.empty() && a［st.top()］>a［j］) {

11int k=st.top(); st.pop();//退栈k

12int length=j-st.top()-1;

13int area=a［k］*length;

14ans=max(ans,area);

15}

16st.push(j);//j进栈

17}

18return ans;

19}

20};



提交运行： 



结果：通过;时间：136ms;空间：75.4MB



由于在a的前面插入0的时间为O(n)，可以改为仅在a的后面插入0，当遍历到a［j］时，如果栈不为空且栈顶柱子k的高度a［k］大于a［j］，将柱子k出栈; 如果栈为空,则置length=j。对应的算法如下。

 C++： 





1class Solution {

2public:

3int largestRectangleArea(vector<int>& a) {

4a.push_back(0);

5int n=a.size();

6stack<int> st;//大顶栈

7int ans=0;//存放最大矩形面积，初始为0

8for(int j=0;j<n;j++) {//遍历a

9while(!st.empty() && a［st.top()］>a［j］) {

10int k=st.top(); st.pop();//退栈k

11int length;

12if(st.empty()) length=j;//栈为空时置length为j

13else length=j-st.top()-1;//栈不为空

14int area=a［k］*length;//求a［st.top()+1..j-1］的矩形面积 

15ans=max(ans,area);//维护ans为最大矩形面积

16}

17st.push(j);//j进栈

18}

19return ans;

20}

21};



提交运行： 



结果：通过;时间：120ms;空间：75.4MB



 Python： 



1class Solution:

2def largestRectangleArea(self, a: List［int］) > int:

3a.append(0)

4n,ans=len(a),0

5st=［］

6for j in range(0,n):

7while st and a［st［-1］］>a［j］:

8k=st［-1］; st.pop()#退栈tmp

9length=j-st［-1］-1 if st else j

10area=a［k］*length

11ans=max(ans,area)

12st.append(j)

13return ans



提交运行： 



结果：通过;时间：296ms;空间：25.8MB



3．4．6LeetCode42——接雨水★★★

【问题描述】给定 n个非负整数的数组a,表示每个宽度为1的柱子的高度图，计算按此排列的柱子下雨之后能接多少雨水。

例如，a=［0，1，0，2，1，0，1，3，2，1，2，1］，如图3．17所示，可以接6个单位的雨水，答案为6。



图3．17一个高度图


【限制】n=height．length，1≤n≤2×104，0≤height［i］≤105。

【解题思路】用单调递减栈找多个元素的共同右边界。先用穷举法求解，用ans存放答案(初始为0)，用k从1到n-1遍历a(前后两个柱子不用考虑)，找到其左边最大高度max_left和右边最大高度max_right，求出max_left和max_right中的最小值minh，对于柱子k而言，上面接的雨水量为minh-a［k］(a［k］<mink)，对于每个柱子k累计这个值到ans中，最后返回ans即可。对应的算法如下。

 C++： 



1class Solution {

2public:

3int trap(vector<int>& a) {

4int n=a.size();

5int ans=0;

6for(int k=1;k<n-1;k++) {

7int max_left=0;//求左边最大高度

8for(int i=k-1;i>=0;i--) {

9if(a［i］>max_left)max_left=a［i］;





10}

11int max_right=0;//求右边最大高度

12for(int j=k+1;j<n;j++) {

13if(a［j］>max_right) max_right=a［j］;

14}

15int minh=min(max_left,max_right);

16if(minh>a［k］) ans+=(minh-a［k］);

17}

18return ans;

19}

20};



提交运行： 



结果：超时(322个测试用例中通过了321个)



上述过程是按列求接雨水量，算法的时间复杂度为O(n2)。另外也可以按层求接雨水量，例如，将图3．17中高度0~1看成第1层，高度1~2看成第2层，高度2~3看成第3层，求出第1层的接雨水量为1+1=2，第2层的接雨水量为3+1=4，第3层的接雨水量为0，总的接雨水量为2+4+0=6。这种按层求解的穷举算法的时间复杂度为O(m×n)，其中m为最大高度值。

可以进一步用单调栈提高性能，设置单调递减栈（小顶栈）st，ans表示答案(初始为0)，用i从0开始遍历a： 

(1) 若栈为空，则直接将i进栈。

(2) 若栈不为空且栈顶柱子k的高度a［k］大于或等于a［i］，说明柱子i会有积水，则直接将i进栈。

(3) 若栈不为空且栈顶柱子k的高度a［k］小于a［i］，说明之前的积水到这里停下，可以计算一下有多少积水。计算方式是出栈柱子k，以新栈顶柱子st．top()为左边界l，柱子i为右边界r，求出接雨水矩形(不含柱子l和柱子r)的高度h为min(a［r］，a［l］)-a［k］，宽度为r-l-1，则将接雨水量(r-l-1)×h累计到ans中。

在上述过程中每个柱子仅进栈和出栈一次，所以算法的时间复杂度为O(n)。

例如，a=［4，2，1，0，1，2，4］，其高度图如图3．18所示，求其接雨水量的过程如下。



图3．18a=［4，2，1，0，1，2，4］

(1) 遍历到a［0］，栈为空，将a［0］进栈； 遍历到a［1］，a［0］≥a［1］，将a［1］进栈； 遍历到a［2］，a［1］≥a［2］，将a［2］进栈； 遍历到a［3］，a［2］≥a［3］，将a［3］进栈，如图3．19(a)所示，st=［0［4］，1［2］，2［1］，3［0］］。

(2) 遍历到a［4］，栈顶a［3］<a［4］，出栈a［3］，st=［0［4］，1［2］，2［1］］，求出以新栈顶a［2］为左边界、以a［4］作为右边界的接雨水量=1。新栈顶a［2］<a［4］不成立，结束，再将a［4］进栈，st=［0［4］，1［2］，2［1］，4［1］］，如图3．19(b)所示。

(3) 遍历到a［5］，栈顶a［4］<a［5］，出栈a［4］，st=［0［4］，1［2］，2［1］］，新栈顶为左边界l=2，右边界r=5，高度h为min(a［r］，a［l］)-a［4］=0，对应的接雨水量=0。新栈顶a［2］<a［5］，出栈a［2］，st=［0［4］，1［2］］，新栈顶为左边界l=1，右边界r=5，高度h为min(a［r］，a［l］)-a［2］=1，对应的接雨水量为(r-l-1)×h=3×1=3。再将a［5］进栈，st=［0［4］，1［2］，5［2］］，如图3．19(c)所示。

(4) 遍历到a［6］，栈顶a［5］<a［6］，出栈a［5］，st=［0［4］，1［2］］，新栈顶为左边界l=1，右边界r=6，高度h为min(a［r］，a［l］)-a［5］=0，对应的接雨水量=0。新栈顶a［1］<a［6］，出栈a［1］，st=［0［4］］，新栈顶为左边界l=0，右边界r=6，高度h为min(a［r］，a［l］)-a［1］=2，对应的接雨水量为(r-l-1)×h=5×2=10。再将a［6］进栈，st=［0［4］，6［4］］，如图3．19(d)所示。



图3．19求a=［4，2，1，0，1，2，4］接雨水量的过程


总的接雨水量ans为1+3+10=14。

又如，a=［1，0，2，1，0，1，3，2，1，2］，求接雨水量的过程如图3．20所示。

(1) a［2］=2出现递增，触发计算出a［1］的接雨水量=1。

(2) a［5］=1出现递增，触发计算出a［4］的接雨水量=1。

(3) a［6］=3出现递增，触发计算出a［3．．5］的接雨水量=3。

(4) a［9］=2出现递增，触发计算出a［8］的接雨水量=1。



图3．20求a=［1，0，2，1，0，1，3，2，1，2］接雨水量的过程


总的接雨水量为1+1+3+1=6。对应的算法如下。


 C++： 



1class Solution {

2public:

3int trap(vector<int>& a) {

4int n=a.size();

5int ans=0;

6stack<int> st;//小顶栈

7for(int i=0;i<n;i++) {

8while(!st.empty() && a［st.top()］<a［i］) {

9int k=st.top(); st.pop();

10if(!st.empty()) {

11int l=st.top();

12int r=i;

13int h=min(a［r］,a［l］)-a［k］;

14ans+=(r-l-1)*h;

15}

16}

17st.push(i);

18}

19return ans;

20}

21};



提交运行： 



结果：通过;时间：16ms;空间：19.9MB



 Python： 



1class Solution:

2def trap(self, a: List［int］) > int:

3ans=0

4st=［］

5for i in range(0,len(a)):

6while st and a［st［-1］］<a［i］:

7k=st［-1］; st.pop()

8if len(st)>0:

9l,r=st［-1］,i

10h=min(a［r］,a［l］)-a［k］

11ans+=(r-l-1)*h

12st.append(i)

13return ans



提交运行： 



结果：通过;时间：56 ms;空间：16.5MB



推荐练习题
1． LeetCode85——最大矩形★★★

2． LeetCode150——逆波兰表达式求值★★

3． LeetCode224——基本计算器★★★

4． LeetCode227——基本计算器Ⅱ★★

5． LeetCode402——移掉k位数字★★

6． LeetCode456——132模式★★

7． LeetCode678——有效的括号字符串★★

8． LeetCode735——行星碰撞★★

9． LeetCode856——括号的分数★★

10． LeetCode921——使括号有效的最少添加★★

11． LeetCode1019——链表中的下一个更大结点★★

12． LeetCode1172——餐盘栈★★★

13． LeetCode1190——反转每对括号间的子串★★

14． LeetCode1209——删除字符串中所有的相邻重复项Ⅱ★★

15． LeetCode1472——设计浏览器历史记录★★

16． LeetCode1504——统计全1子矩形★★

17． LeetCode1598——文件夹操作日志搜集器★

18． LeetCode1653——使字符串平衡的最少删除次数★★

19． LeetCode1717——删除子字符串的最大得分★★

20． LeetCode2296——设计一个文本编辑器★★★

21． LeetCode2390——从字符串中移除星号★★

22． LeetCode2434——使用机器人打印字典序最小的字符串★★

23． LeetCode2345——寻找可见山的数量★★