算法面试

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

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

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

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容器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 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向量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链表容器作为val栈(每个结点对应一个地址，将其尾部作为栈顶)，另外设计一个map::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 valst;//用链表作为val栈

4map::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 st;

6for(int i=0;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

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 buildArray(vector& target,int n) {

4vector 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& pushed, vector& popped) {

4stack st;

5int j=0;

6for(int i=0;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 st;

5for(int i=0;i