新書推薦：
《
向上流动：求学与原生家庭的羁绊
》
售價：NT$
301.0
《
大国金融：全球金融变局下的中国机会（解读全球金融体系，变局前因后果，金融危机的根源与演化逻辑，中国特色金融，现代金融体系）
》
售價：NT$
347.0
《
如何拥抱一只刺猬（漫画版）
》
售價：NT$
305.0
《
万千心理·拉康精神分析的临床概念化
》
售價：NT$
551.0
《
超级沟通者 与所有人连接的秘密
》
售價：NT$
352.0
《
工匠、商人与银行家：文艺复兴时期的佛罗伦萨经济
》
售價：NT$
857.0
《
7步成交
》
售價：NT$
305.0
《
维柯讲疏
》
售價：NT$
607.0
|
| 編輯推薦： |
|
本书适合于需要进行算法面试的读者，通过阅读本书可以掌握算法面试中求解问题的方法和技巧，提升自己的算法技能和思维方式，从而在面试中脱颖而出。同时，本书可以作为“数据结构”和“算法设计与分析”课程的辅导书，也可以供各种程序设计竞赛和计算机编程爱好者研习。
|
| 內容簡介： |
本书旨在帮助读者更好地应对算法面试，提高算法和编程能力。书中按专题精选了LeetCode平台的一系列的热点算法题，并详细解释其求解思路和过程。全书分为三个部分，第Ⅰ部分为数据结构及其应用，以常用数据结构为主题，深入讲解各种数据结构的应用方法和技巧。第Ⅱ部分为算法策略及其应用，以基本算法设计方法和算法设计策略为主题，深入讲解各种算法设计策略的应用方法和技巧。第Ⅲ部分为经典问题及其求解，以实际中的一些问题为主题，深入讲解这些问题多种求解方法。
本书适合于需要进行算法面试的读者，通过阅读本书可以掌握算法面试中求解问题的方法和技巧，提升自己的算法技能和思维方式，从而在面试中脱颖而出。同时可以作为《数据结构》和《算法设计与分析》课程的辅导书，也可以供各种程序设计竞赛和计算机编程爱好者研习。
目录
|
| 關於作者： |
|
李春葆，计算机学院教授，主要研究方向：数据挖掘、人工智能和软件工程。发表论文30余篇，主持和参加多项科研课题。著作教材多部。从事近30年C/C 语言、数据结构和算法设计等课程的第一线本科教学工作，具备丰富的教学经验，曾参与深圳名企的笔试和面试题库建设。
|
| 目錄：
|
扫一扫
配套资源
第一部分数据结构及其应用
第1章数组
1.1数组概述
1．1．1数组的定义
1．1．2数组的知识点
1．2数组的基本算法设计
1．2．1LeetCode27——移除元素★
1．2．2LeetCode283——移动0★
1．2．3LeetCode2460——对数组执行操作★
1．2．4LeetCode75——颜色的分类★★
1．2．5LeetCode189——轮转数组★★
1．3有序数组的算法设计
1．3．1LeetCode26——删除有序数组中的重复项★
1．3．2LeetCode80——删除有序数组中的重复项Ⅱ★★
1．3．3LeetCode1287——有序数组中出现次数超过元素总数25%的
元素★
1．3．4LeetCode1200——最小绝对差★
1．3．5LeetCode88——合并两个有序数组★
1．3．6LeetCode349——两个数组的交集★
1．3．7LeetCode977——有序数组的平方★
1．3．8LeetCode1470——重新排列数组★
1．3．9LeetCode1213——3个有序数组的交集★
1．3．10LeetCode264——丑数Ⅱ★★
1．3．11LeetCode373——查找和最小的k对数字★★
推荐练习题
第2章链表
2．1链表概述
2．1．1链表的定义
2．1．2链表的知识点
2．2链表基本操作的算法设计
2．2．1LeetCode203——移除链表元素★
2．2．2LeetCode206——反转链表★
2．2．3LeetCode328——奇偶链表★★
2．2．4LeetCode61——旋转链表★★
2．2．5LeetCode141——环形链表★
2．2．6LeetCode138——复制带随机指针的链表★★
2．2．7LeetCode707——设计链表★★
2．3链表的分组算法设计
2．3．1LeetCode92——反转链表Ⅱ★★
2．3．2LeetCode24——两两交换链表中的结点★★
2．3．3LeetCode25——k个一组翻转链表★★★
2．4有序链表的算法设计
2．4．1LeetCode83——删除排序链表中的重复元素★
2．4．2LeetCode82——删除排序链表中的重复元素Ⅱ★★
2．4．3LeetCode21——合并两个有序链表★
2．4．4LeetCode23——合并k个有序链表★★★
2．4．5LeetCode1634——求两个多项式链表的和★★
推荐练习题
第3章栈
3．1栈概述
3．1．1栈的定义
3．1．2栈的知识点
3．2扩展栈的算法设计
3．2．1LeetCode1381——设计一个支持增量操作的栈★★
3．2．2LeetCode155——最小栈★
3．2．3LeetCode716——最大栈★★★
3．3栈应用的算法设计
3．3．1LeetCode1544——整理字符串★★
3．3．2LeetCode71——简化路径★★
3．3．3LeetCode1441——用栈操作构建数组★
3．3．4LeetCode946——验证栈序列★★
3．3．5LeetCode20——有效的括号★
3．3．6LeetCode1249——删除无效的括号★★
3．3．7LeetCode32——最长的有效括号子串的长度★★★
3．4单调栈应用的算法设计
3．4．1LeetCode503——下一个更大元素Ⅱ★★
3．4．2LeetCode496——下一个更大元素Ⅰ★
3．4．3LeetCode739——每日温度★★
3．4．4LeetCode316——去除重复字母★★
3．4．5LeetCode84——柱状图中最大的矩形★★★
3．4．6LeetCode42——接雨水★★★
推荐练习题
第4章队列和双端队列
4．1队列和双端队列概述
4．1．1队列和双端队列的定义
4．1．2队列和双端队列的知识点
4．2扩展队列的设计
4．2．1LeetCode622——设计循环队列★★
4．2．2LeetCode641——设计循环双端队列★★
4．2．3LeetCode1670——设计前中后队列★★
4．2．4LeetCode232——用栈实现队列★
4．3队列的应用
4．3．1LeetCode1700——无法吃午餐的学生的数量★
4．3．2LeetCode933——最近的请求次数★
4．3．3LeetCode225——用队列实现栈★
4．3．4LeetCode281——锯齿迭代器★★
4．3．5LeetCode1047——删除字符串中所有的相邻重复项★
4．4单调队列
4．4．1LeetCode239——滑动窗口的最大值★★★
4．4．2LeetCode1438——绝对差不超过限制的最长连续子数组★★
4.4.3LCR184——设计自助结算系统★★
推荐练习题
第5章哈希表
5．1哈希表概述
5．1．1哈希表的定义
5．1．2哈希表的知识点
5.2哈希表的实现
5．2．1LeetCode705——设计哈希集合★
5．2．2LeetCode706——设计哈希映射★
5．3哈希集合应用的算法设计
5．3．1LeetCode349——两个数组的交集★
5．3．2LeetCode202——快乐数★
5．3．3LeetCode217——存在重复元素★
5．3．4LeetCode379——电话目录管理系统★★
5．3．5LeetCode128——最长连续序列★★
5．3．6LeetCode41——缺失的第一个正数★★★
5．3．7LeetCode1436——旅行终点站★
5．4哈希映射应用的算法设计
5．4．1LeetCode350——两个数组的交集Ⅱ★
5．4．2LeetCode1460——通过翻转子数组使两个数组相等★
5．4．3LeetCode383——赎金信★
5．4．4LeetCode347——前k个高频元素★★
5．4．5LeetCode242——有效的字母异位词★
5．4．6LeetCode205——同构字符串★
5．4．7LeetCode1——两数之和★
5．4．8LeetCode219——存在重复元素Ⅰ★
5．4．9LeetCode49——字母异位词的分组★★
5．4．10LeetCode249——移位字符串的分组★★
推荐练习题
第6章二叉树
6．1二叉树概述
6．1．1二叉树的定义
6．1．2二叉树的知识点
6．2二叉树先序、中序和后序遍历应用的算法设计
6．2．1LeetCode144——二叉树的先序遍历★
6．2．2LeetCode94——二叉树的中序遍历★
6．2．3LeetCode145——二叉树的后序遍历★
6．2．4LeetCode965——单值二叉树★
6．2．5LeetCode100——相同的树★
6．2．6LeetCode572——另一棵树的子树★
6．2．7LeetCode543——二叉树的直径★
6．2．8LeetCode563——二叉树的坡度★
6．2．9LeetCode2331——计算二叉树的布尔运算值★
6．2．10LeetCode199——二叉树的右视图★★
6．2．11LeetCode662——二叉树的最大宽度★★
6．3二叉树层次遍历应用的算法设计
6．3．1LeetCode102——二叉树的层次遍历★★
6．3．2LeetCode199——二叉树的右视图★★
6．3．3LeetCode637——二叉树的层平均值★
6．3．4LeetCode2471——逐层排序二叉树所需的最少操作数目★★
6．3．5LeetCode2415——反转二叉树的奇数层★★
6．3．6LeetCode1602——找二叉树中最近的右侧结点★★
6．4构造二叉树的算法设计
6．4．1LeetCode105——由先序与中序遍历序列构造二叉树★★
6．4．2LeetCode106——由中序与后序遍历序列构造二叉树★★
6．4．3LeetCode2196——根据描述创建二叉树★★
6．5二叉树序列化的算法设计
6．5．1LeetCode297——二叉树的序列化与反序列化★★★
6．5．2LeetCode100——相同的树★
6．5．3LeetCode572——另一棵树的子树★
推荐练习题
第7章二叉搜索树
7．1二叉搜索树概述
7．1．1二叉搜索树的定义
7．1．2二叉搜索树的知识点
7．2二叉搜索树基本操作的算法设计
7．2．1LeetCode1008——先序遍历构造二叉搜索树★★
7．2．2LeetCode700——二叉搜索树中的搜索★
7．2．3LeetCode701——二叉搜索树中的插入操作★★
7．2．4LeetCode450——删除二叉搜索树中的结点★★
7．3二叉搜索树特性的算法设计
7．3．1LeetCode270——最接近的二叉搜索树值★
7．3．2LeetCode235——二叉搜索树的最近公共祖先★★
7．3．3LeetCode938——二叉搜索树的范围和★
7．3．4LeetCode669——修剪二叉搜索树★★
7．3．5LeetCode776——拆分二叉搜索树★★
7．3．6LeetCode285——二叉搜索树中的中序后继★★
7．3．7LeetCode255——验证先序遍历序列二叉搜索树★★
7．4二叉搜索树基于中序遍历的算法设计
7．4．1LeetCode783——二叉搜索树结点的最小距离★
7．4．2LeetCode230——二叉搜索树中第k小的元素★★
7．4．3LeetCode98——验证二叉搜索树★★
7．4．4LeetCode538——把二叉搜索树转换为累加树★★
7．4．5LeetCode99——恢复二叉搜索树★★
7．4．6LeetCode173——二叉搜索树迭代器★★
7．4．7LeetCode272——最接近的二叉搜索树值Ⅱ★★★
推荐练习题
第8章平衡二叉树
8．1平衡二叉树概述
8．1．1平衡二叉树的定义
8．1．2平衡二叉树的知识点
8．2构造平衡二叉树的算法设计
8．2．1LeetCode108——将有序数组转换为平衡二叉树★
8．2．2LeetCode109——将有序链表转换为平衡二叉树★★
8．2．3LeetCode1382——将二叉搜索树转换为平衡二叉树★★
8．3平衡树集合应用的算法设计
8．3．1LeetCode506——相对名次★
8．3．2LeetCode414——第三大的数★
8．3．3LeetCode855——考场就座★★
8．3．4LeetCode2353——设计食物评分系统★★
8．4平衡树映射应用的算法设计
8．4．1LeetCode846——一手顺子★★
8．4．2LeetCode981——基于时间的键值存储★★
8．4．3LeetCode1912——设计电影租借系统★★★
推荐练习题
第9章优先队列
9．1优先队列概述
9．1．1优先队列的定义
9．1．2优先队列的知识点
9．2优先队列的实现
9．2．1LeetCode912——排序数组★★
9．2．2LeetCode215——数组中第k个最大的元素★★
9．2．3LeetCode506——相对名次★
9．3优先队列应用的算法设计
9．3．1LeetCode703——数据流中第k大的元素★
9．3．2LeetCode373——查找和最小的k对数字★★
9．3．3LeetCode23——合并k个有序链表★★★
9．3．4LeetCode239——滑动窗口的最大值★★★
9．3．5LeetCode1383——最大的团队表现值★★★
9．3．6LeetCode2462——雇佣k位工人的总代价★★
推荐练习题
第10章并查集
10．1并查集概述
10．1．1并查集的定义
10．1．2并查集的实现
10．1．3带权并查集
10．2一维并查集应用的算法设计
10．2．1LeetCode261——以图判树★★
10．2．2LeetCode323——无向图中连通分量的数目★★
10．2．3LeetCode684——冗余连接★★
10．2．4LeetCode785——判断二分图★★
10．2．5LeetCode990——等式方程的可满足性★★
10．2．6LeetCode1061——按字典序排列最小的等价字符串★★
10．2．7LeetCode947——移除最多的同行或同列石头★★
10．3二维并查集
10．3．1LeetCode200——岛屿的数量★★
10．3．2LeetCode1559——在二维网格图中探测环★★
10．4带权并查集
10．4．1LeetCode695——最大岛屿的面积★★
10．4．2LeetCode128——最长连续序列★★
10．4．3LeetCode1254——统计封闭岛屿的数目★★
10．4．4LeetCode399——除法求值★★
推荐练习题
第11章前缀和与差分
11．1前缀和与差分概述
11．1．1前缀和
11．1．2差分
11．2一维前缀和应用的算法设计
11．2．1LeetCode724——寻找数组的中心下标★
11．2．2LeetCode238——除自身以外数组的乘积★★
11．2．3LeetCode1749——任意子数组和的绝对值的最大值★★
11．2．4LeetCode1524——和为奇数的子数组的数目★★
11．2．5LeetCode560——和为k的子数组★★
11．2．6LeetCode325——和等于k的最长子数组的长度★★
11．2．7LeetCode523——连续子数组和★★
11．2．8LeetCode53——最大子数组和★★
11．3二维前缀和应用的算法设计
11．3．1LeetCode304——二维区域和检索(矩阵不可变)★★
11．3．2LeetCode1074——元素和为目标值的子矩阵的数量★★★
11．3．3面试题17．24——最大子矩阵★★★
11．4差分数组应用的算法设计
11．4．1LeetCode370——区间加法★★
11．4．2LeetCode1109——航班预订统计★★
11．4．3LeetCode2536——子矩阵元素加1★★
推荐练习题
第12章线段树
12．1线段树概述
12．1．1线段树的定义
12．1．2简单线段树的实现
12．1．3复杂线段树的实现
12．1．4线段树的动态开点实现
12．1．5离散化
12．2简单线段树应用的算法设计
12．2．1LeetCode303——区域和检索(数组不可变)★
12．2．2LeetCode308——二维区域和检索(可改)★★★
12．2．3LeetCode327——区间和的个数★★★
12．3复杂线段树应用的算法设计
12．3．1LeetCode715——Range模块★★★
12．3．2LeetCode1622——奇妙序列★★★
12．4离散化在线段树中的应用
12．4．1LeetCode327——区间和的个数★★★
12．4．2LeetCode315——计算右侧小于当前元素的个数★★★
推荐练习题
第13章树状数组
13．1树状数组概述
13．1．1树状数组的定义
13．1．2树状数组的实现
13．2树状数组应用的算法设计
13．2．1LeetCode1649——通过指令创建有序数组★★★
13．2．2LeetCode1409——查询带键的排列★★
13．2．3LeetCode683——k个关闭的灯泡★★★
13．2．4LeetCode308——二维区域和检索(可改)★★★
13．3离散化在树状数组中的应用
13．3．1LeetCode327——区间和的个数★★★
13．3．2LeetCode315——计算右侧小于当前元素的个数★★★
推荐练习题
第14章字典树和后缀数组
14．1字典树和后缀数组概述
14．1．1字典树
14．1．2后缀数组
14．2字典树应用的算法设计
14．2．1LeetCode208——实现Trie(前缀树)★★
14．2．2LeetCode14——最长公共前缀★
14．2．3LeetCode648——单词替换★★
14．2．4LeetCode677——键值映射★★
14．2．5LeetCode792——匹配子序列的单词数★★
14．3后缀数组应用的算法设计
14．3．1LeetCode1698——字符串的不同子串的个数★★
14．3．2LeetCode1044——最长重复子串★★★
推荐练习题
|
| 內容試閱：
|
党的二十大报告指出： 教育、科技、人才是全面建设社会主义现代化国家的基础性、战略性支撑。必须坚持科技是第一生产力、人才是第一资源、创新是第一动力，深入实施科教兴国战略、人才强国战略、创新驱动发展战略，开辟发展新领域新赛道，不断塑造发展新动能新优势。高等教育与经济社会发展紧密相连，对促进就业创业、助力经济社会发展、增进人民福祉具有重要意义。
在现代社会中，算法已经广泛应用于计算机科学的各个领域，如人工智能、数据挖掘、网络安全和生物信息学等。许多成功的案例都证明了算法的重要性和实用性，如搜索引擎的优化、社交网络的推荐系统、医疗诊断的辅助决策等。算法知识和技能对于程序员来说至关重要。算法面试是许多科技公司招聘过程中必不可少的一环，它考查的是候选人的编程能力、思维逻辑、问题解决能力以及算法设计技巧。通过算法面试，候选人可以展示自己的技能和知识，提升自己在求职市场上的竞争力。
LeetCode是一个在线刷题平台，提供了大量的算法题目供用户练习，帮助用户加深对数据结构与算法的理解和掌握。LeetCode于2011年诞生于美国硅谷，2018年2月由上海领扣网络引入中国并正式命名为力扣，其中文网站于同月测试上线，2018年10月力扣全新改版，更加注重于学习体验。许多北美大厂（如谷歌、微软和亚马逊等）在面试中都涉及算法及其相关知识，甚至直接从LeetCode出题(许多北美程序员从实习到全职，再到跳槽，一路上都在刷LeetCode)。国内大厂近几年也越来越重视对算法的考查，如腾讯、百度、华为和字节跳动等都是较看重算法面试的公司。
本书提供一系列编者精心挑选的LeetCode问题，覆盖不同难度级别和C /Python编程语言，旨在帮助读者提高编程技能和更深入地理解数据结构与算法的原理，以应对算法面试中的挑战。
本书内容
本书共25章，分为三部分。
第一部分（第1~14章）为数据结构及其应用，以常用数据结构为主题，深入讲解各种数据结构的应用方法和技巧，包含数组、链表、栈、队列和双端队列、哈希表、二叉树、二叉搜索树、平衡二叉树、优先队列、并查集、前缀和与差分、线段树、树状数组、字典树和后缀数组等。
第二部分（第15~22章）为算法设计策略及其应用，以基本算法设计方法和算法设计策略为主题，深入讲解各种算法设计策略的应用方法和技巧，包含穷举法、递归、分治法、DFS、BFS和拓扑排序、回溯法、分支限界法、A*算法、动态规划和贪心法等。
第三部分（第23~25章）为经典问题及其求解，以实际面试中的一些问题为主题，深入讲解这些问题的多种求解方法，对比分析不同方法的差异，包含跳跃问题、迷宫问题和设计问题等专题。
本书特色
(1) 全面覆盖： 本书对算法面试中可能涉及的各种主题进行了较为全面的覆盖，包括各种基础数据结构和常用的算法设计策略。
(2) 实战导向： 书中精选的许多LeetCode题目都是国内外互联网大厂的热门算法面试题，具有很强的实战性。
(3) 知识的结构化： 本书以数据结构和算法策略为主线，划分为若干知识点，通过实例和问题求解将相关的知识点串起来构成知识网络，不仅可以加深读者对算法原理的理解，而且可以拓宽读者对算法应用的视野。
(4) 求解方法的多维性： 同一个问题采用多种算法策略实现，如迷宫问题采用回溯法、分支限界法、A*算法和贪心法求解等。通过对不同算法策略的比较，使读者更容易体会每种算法策略的设计特点和优缺点，以提高算法设计的效率。
(5) 代码的规范化： 书中代码采用C 和Python语言编写，不仅在LeetCode平台上提交通过，而且进行了精心的代码组织和规范化，包括变量名称和算法策略的统一与标准化等，尽可能提高代码的可读性。
注： 书中以LeetCode开头 序号的题目均来自LeetCode平台。
配套资源获取方式
扫描封底的文泉云盘防盗码，再扫描目录上方的二维码获取。
如何刷题和使用本书
在互联网上和力扣平台上有许多关于LeetCode刷题经验的分享，读者可以酌情参考。编者建议读者在具备一定的数据结构和算法基础后按本书中的专题分类刷题，先刷数据结构部分后刷算法部分，先刷简单题目后刷困难题目(书中题目按难度分为3个级别，即★、★★和★★★，分别对应简单、中等和困难)，在刷题时要注重算法思路和算法实现细节，每个环节都要清清楚楚，并能够做到举一反三，同时将自己在线提交的结果与书中的时间和空间进行对比分析（值得注意的是书中列出的时间和空间是编者提交的结果，后面因环境的变化可能有所不同）。另外，经常进行归纳总结和撰写解题报告是提高编程能力的有效手段。在没有对一道题目进行深入思考和分析之前就阅读书中的代码部分甚至是复制、粘贴代码，这种做法不可取。总之，使用良好的刷题方法并且持之以恒，一定会收获理想的效果。
致谢
本书以LeetCode为平台，书中所有LeetCode题目及其相关内容都得到领扣网络(上海)有限公司的授权。本书的编写得到清华大学出版社魏江江分社长的大力支持，王冰飞老师给予精心编辑。本书在编写过程中参考了众多博客和LeetCode题解评论栏目的博文，编者在此一并表示衷心的感谢。
作者
2024年8月
第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 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 a={1，5，2，4，3};
2stack st;
3for(int i=0;ia［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 None:#进栈x
7if self.top 1 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 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 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 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 st;
8st.push(-1);
9for(int i=0;i 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］ nextGreaterElements(vector& nums) {
4int n=nums.size();
5vector ans(n，-1);
6stack st;//单调递减栈
7for(int i=0;i<2*n-1;i ) {
8while(!st.empty() && nums［st.top()］ List［int］:
3n=len(nums)
4ans，st=［-1］*n，［］
5for i in range(0，2*n-1):
6while len(st) and nums［st［-1］］ nextGreaterElement(vector& nums1， vector& nums2) {
4unordered_map hmap;//哈希表
5int m=nums1.size()，n=nums2.size();
6stack st;//小顶栈
7for(int i=0;i ans(m，-1);//初始化所有元素为-1
14for(int i=0;i List［int］:
3dict={}
4m，n=len(nums1)，len(nums2)
5st=［］#小顶栈
6for i in range(0，n):
7while len(st)>0 and st［-1］ dailyA(vector& a) {
4int n=a.size();
5vector ans(n，0);
6stack st;//小顶栈
7for(int i=0;i List［int］:
3n=len(a)
4ans=［0］*n
5st=［］
6for i in range(0，n):
7while st and a［st［-1］］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&a) {
4int n=a.size();
5int ans=0;
6for(int k=0;k=0 && a［i］>=a［k］) length ;
10int j=k;
11while( 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=4ans=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=6ans=6。
(3) 新栈顶2［2］的高度大于a［5］不成立，将j=5进栈。
从中看出通过单调栈可以一次求出多个柱子的右边界，同时又可以快速求出这些柱子的左边界。尽管在算法中使用了两重循环，实际上每个柱子最多进栈、出栈一次，所以算法的时间复杂度为O(n)。对应的算法如下。
C ：
1class Solution {
2public:
3int largestRectangleArea(vector&a) {
4a.insert(a.begin()，0);
5a.push_back(0);
6int n=a.size();
7stack st;//大顶栈
8int ans=0;//存放最大矩形面积，初始为0
9for(int j=0;ja［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& a) {
4a.push_back(0);
5int n=a.size();
6stack st;//大顶栈
7int ans=0;//存放最大矩形面积，初始为0
8for(int j=0;ja［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］& a) {
4int n=a.size();
5int ans=0;
6for(int k=1;k=0;i--) {
9if(a［i］>max_left)max_left=a［i］;
10}
11int max_right=0;//求右边最大高度
12for(int j=k 1;jmax_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) {
4int n=a.size();
5int ans=0;
6stack st;//小顶栈
7for(int i=0;i int:
3ans=0
4st=［］
5for i in range(0，len(a)):
6while st and a［st［-1］］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——寻找可见山的数量★★
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
