下载掌阅APP，畅读海量书库
立即打开
【问题描述】 给定一个循环数组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≤10 4 ，-10 9 ≤nums[ i ]≤10 9 。
【解题思路】 使用单调栈求下一个更大元素 。先不考虑循环，对于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++：
提交运行：
Python：
提交运行：
【问题描述】 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 ]≤10 4 ，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++：
提交运行：
Python：
提交运行：
【问题描述】 给定一个整数数组 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≤10 5 ，30≤ a [ i ]≤100。
【解题思路】 使用单调栈求下一个更大元素 。本题与3.4.2节类似，仅将求当前元素的下一个更大元素改为求当前元素与其下一个更大元素之间的距离。同样使用单调递减栈（小顶栈）求解，对应的算法如下。
C++：
提交运行：
Python：
提交运行：
【问题描述】 给定一个字符串s，请去除字符串中重复的字母，使得每个字母只出现一次，并且保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
例如，s=＂cbacdcbc＂，答案为＂acdb＂。
【限制】 1≤s.length≤10 4 ，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。
（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＂。
【问题描述】 给定 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++：
提交运行：
上述算法的时间复杂度为 O （ n 2 ），出现超时的情况。可以使用单调递增栈（大顶栈）提高性能，为了设置高度数组 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.16 a =[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++：
提交运行：
由于在 a 的前面插入0的时间为 O （ n ），可以改为仅在 a 的后面插入0，当遍历到 a [ j ]时，如果栈不为空且栈顶柱子 k 的高度 a [ k ]大于 a [ j ]，将柱子 k 出栈；如果栈为空，则置length= j 。对应的算法如下。
C++：
提交运行：
Python：
提交运行：
【问题描述】 给定 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×10 4 ，0≤height[ i ]≤10 5 。
【解题思路】 用单调递减栈找多个元素的共同右边界 。先用穷举法求解，用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++：
提交运行：
上述过程是按列求接雨水量，算法的时间复杂度为 O （ n 2 ）。另外也可以按层求接雨水量，例如，将图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.18 a =[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++：
提交运行：
Python：
提交运行：
