Leetcode按题目类型总结(十一)

堆、栈和队列

Posted by Jingming on November 17, 2017

所有代码详见:https://github.com/jingminglake/Leetcode

总体思路

关于序列中最大最小值的问题常使用的数据结构:

  • 优先级队列

堆(优先级队列),耗时O(logn)插入元素,O(1)时间读取最小(大)值(堆顶),O(logn)时间删除堆顶。

PS.(1)堆和优先级队列的关系:堆是一种具体的数据结构,他的实现可以是数组、链表或者其它,但是从逻辑上来看,二叉堆就是一个完全二叉树。优先级队列是一种抽象数据结构,支持查找,插入和删除元素,不过,删除和查找元素的操作都是只能访问堆中的优先级最大(或最小)的元素。

也就是说,堆是实现优先级队列的一种方式(其他方式例如可以用平衡二叉搜索树来实现),而且是很好的一种方式(所有操作的时间复杂度均为O(logn))。堆和优先级队列关注的点不一样,前者关注一个二叉堆的性质,后者关注的是某种队列的性质。实际上二者基本是一种东西:解决的问题一样,只不过堆的结构更加具体。

(2)优先级队列找第k大(小)

几种思路:第一种是把所有n个元素放入大顶堆,然后弹出n-k+1个不符合要求的元素(比第k大的元素),这样堆顶就是符合要求的元素;第二种是把所有n个元素放入小顶堆,然后弹出第k个元素,就是答案;

第三种是维持一个大小为k的大顶堆,当堆顶大小达到k之后,那么显然,堆顶的元素是该堆中k个元素中最大的,那么我们需要做的就是把所有元素一个个的加入堆,一旦堆的大小大于k,那么就去除掉一个,因为这个元素显然比k+1个元素还大,所以做不成k,最后堆顶就是答案。

前两种思路的坏处在于,时间、空间复杂度过大,例如n很大,而k比较小。第三种方式时间复杂度不变的情况下,只需花费O(k)的空间, O(nlogk)的时间。

所以,解题时候一定要使用第三种思路,这样,在k很小(10以内的题目都非常适用)的情况下,时间接近是线性的。

  • min-queue

使用min-queue,耗时O(1)读取最小值,但是注意是只能O(1)读,不能O(1)删最小值。

  • treeset

使用treeset(c++的treeset就是set和multiset,其中multiset支持元素重复,优先级队列是允许重复的)。好处是可以O(logn)时间删除任意的结点(而不仅是删除最大或最小结点),如果是求序列中的最大值,那么我们可以在存储时候存储负数,那么最大值就会在第一个位置了。如果输入序列是包含重复的,那么可以设计一个二元组(位置,元素)往treeset中存,或者使用包含重复的treeset(c++中就是multiset)。

  • 单调栈

适用于寻找数组中元素第一个满足条件的邻居。

具体题目

295. Find Median from Data Stream

题意:设计数据结构从数据流中取出中位数。

:每次取出中位数时间复杂度为O(logN)的解法:

使用两个堆(c++中的priority_queue默认是一个最大堆),左边的堆为最大堆,右边堆为最小堆,这样保证左堆顶比右堆顶小的时候,就能保证严格的左边小于右边,

与此同时,还要维持一个性质,就是要保证左边堆的元素等于右边堆的元素或者只能多1个元素,且左堆顶要小于等于右堆顶。这样,如果左堆数量比右堆大1,中位数显然在左边堆的堆顶;如果左右堆一样大,那么根据题意中位数取左堆和右堆堆顶的平均值。

每次插入元素的时候,要维持这样两个性质,也就是需要调整。

add元素的调整过程: 先加入左堆,与较小的一半进行比较,由于加入的元素可能属于右堆,所以要把左堆堆顶弹出给右堆,这样意味着右堆大小增大了1,之前是左堆等于或者比右堆大1,现在就是左右堆相等或者右堆大1。其中的右堆比左堆大1违反了性质,此时把右堆堆顶取出来加入左堆,这样左堆比右堆大1。这样满足不变式性质。

也可以在加入时候,从堆顶判断应该加入哪个堆,如果是左堆,那么要注意左堆不为空才能比较堆顶,以及左边堆不能超过右边堆2个元素。如果是右堆,那么也要保证右堆不大于左堆。 推荐第一种。

PS. c++中,对于数值使用最小堆的技巧是,每次push的时候,push该数的负数(正变负,负变正),取出来使用的时候在还原。

239. Sliding Window Maximum

题意:取出滑动窗口中最大值,一次取一个,结果是一个序列。

:此题如果使用multiset,时间复杂度是O(nlogk)。

O(n)的解法:使用双端队列。队列存放当前扫描序列中的最大值的数组下标。每次扫描新元素时候,都会先从队列左端开始去除队列中不符合要求(落在窗口外)的下标(直到满足或者为空),然后再看当前元素是不是比队列右端下标对应的元素大,大的话就说明右端元素不符合要求,去除掉,直到右端比当前元素小或者队列为空,最后,无论如何都加入当前元素下标到队列右端,再从队列左端就是当前滑动窗口的最大值。

双端队列相当于可以从栈底进行删除的单调栈。双端队列的头部(左侧)就是结果(落在窗口内的最大值),后面放着的单调递减的比最大值小的值且下标递增的比队列头要大的值,也就是等将来队列头失效后可以充当当前最大值替补的值。

480. Sliding Window Median

题意:每次移动滑动窗口,并从窗口中取出中位数。

:此题与295题相似,区别在于左堆和右堆的总元素个数大于窗口大小时候,要删除元素。所以此题不能像295题那样使用priority_queue了,而要使用multiset。使用multiset之后,求最大的数的时候,也可以不存负数,而是使用–end()来取最大值。

此题流程是,在两堆元素数量大于窗口大小时先删去由于更新窗口落在外面的元素,使左右堆满足条件,例如(5,4)变为(5,3)或(4,4),其中(5,3)需要调整;(5,5)可以变为(4,5)或者(5,4),其中(4,5)需要调整,调整之后其余按295题目方法来处理。

也可以只使用一个multiset,不过每次要使用库函数next来取得当前set中的某个迭代器的第n个后继。

692. Top K Frequent Words

题意:输出前k频率的单词,单词如果频率相同,那么按字母排序。

:使用优先级队列,队列大小严格控制为k,然后,将单词和单词出现次数的键值对加入队列,排序按照频率,如果频率相同,则看单词之间大小。然后,弹出队列所有数到res,然后翻转res即可。

PS.此题是很好的使用优先级队列的例子,很好的lambda使用语法形式。

https://github.com/jingminglake/Leetcode/blob/master/topKFrequentWords/topKFrequentWords.cpp

对于优先级队列比较运算符的心得:其实本质和vector是一样的,只不过pq的top相当于vector的最后一个元素,因此vector看起来是递增的,但是如果把vector当作队列,那么队列头其实是最大的元素,就是“最大堆”。

215. Kth Largest Element in an Array

题意:找出无序数组中第k个最大的数,注意,与第k大的数不同,第k个最大数,是指第n-k+1大的数。

:此题解法多样:第一种是quickselect。

第二种是使用优先级队列。使用优先级队列的两种思路是: (1)保持一个k大小的“小根堆”的队列,此小根堆里面维持了整个数组最大的k个数。所以堆顶就是要求的第k大的数。此小根堆的更新时机是:如果不足k个数,那么直接入堆,否则,必须比堆顶大才能入堆,因为这样才能保证小根堆的里面最终是最大的k个数。时间复杂度:O(nlogk)。

(2)保持一个n - k + 1大小的“大根堆”队列,此大根堆里面维持的是数组中最小的n - k + 1个数。所以堆顶就是要求的数。更新时机:先push元素,在检查队列的大小是否大于n - k + 1,如果是那么弹出其中最大的那个数,也就是堆顶。这种方法相当于比kth大的元素放进去又立即弹出来。时间复杂度: O( (n-k+1)log(n -k + 1) + k)。 注意:尽量使用第一种算法。先看k的大小,如果k比较大,那么转换为计算第n - k + 1小的数。一般情况下,也就是k比较小的时候,一定要保证优先级队列的大小比较小,也就是使得二叉堆的树高比较低,所以一定要使用与n无关的算法,也就是要采取k大小的二叉堆,然后再根据题意来看使用大堆还是小堆。一般的思路就是,先无论怎么样,先放入k个元素到队列中,然后从第k+1个开始进行考虑,一般是放入队列后把队列的头弹出来。时间复杂度是O(nlogk)。

218. The Skyline Problem

题意:三元组(L,R,H)表示建筑物(矩形),由于建筑物的底边都是在x轴上,所以只需要用L,R来描述建筑物的水平位置,使用H来描述建筑物的高。现在给出这样的一组三元组,求出建筑物的轮廓线,轮廓线使用(X,Y)来表示,也就是一组二维坐标点,这些点相近俩俩组合就能得出轮廓线。

:使用sweepline。先把所有的三元组(L,R,H)拆分为(L,H)和(R,-H),表示的含义是,前者是高度覆盖范围的开端,后者是高度覆盖范围的结束。

然后将所有正方形拆分后的pair进行排序,横坐标小的排前面,如果横坐标相同,那么按高度(绝对值)来排。排好之后,开始sweep横坐标,使用multiset的存放当前有效的高度:如果是起始点,那么把高度存到multiset里,如果是消失点的话,那么需要删除当前高度(c++的优先级队列不支持删除操作,而multiset可以)。

无论是起始点还是消失点,都可能会带来轮廓的变化,例如起始点的高度很高,会挡住之前的最高点,或者消失点的高度很高,消失后会将挡住的第二高的显示出来。这种第二高的保存需要使用multiset。

注意的是,如果消失点当前高度和multiset里面很多高度相等的时候是不应该记录。所以,应该比较的其实是此时的最大高度与之前高度比是否发生变化。每次从multiset里取出最大的与当前高度进行比较,如果与之前高度不等,那么就是新轮廓点,记录到结果中。如果遇到消失时机,那么从multiset里删除相应的高度。

关键就是:当前扫描到的点的最高点与之前有效的最高点高度不一样的话,就记录。也就是二叉平衡搜索树的顶点发生变化的时候,但是注意一开始扫描线高度为0。

PS.横坐标相同的时候,起始点排消失点前面。

此题数据结构的本质是考虑二叉平衡搜索树顶点由于每次加入一个新元素带来的变化,也就是如何动态的排序一组元素。

716. Max Stack

题意:实现max stack数据结构,O(1)时间能够得出最大值,还要实现删除最大值的操作。

:此题解题思路和min stack一样,区别是:此题多一个弹出最大值的操作,解决方法是,新建一个临时栈,然后从max stack弹出值(去除掉其中的替补值)暂时存到新建的栈上,其中,遇到最大值就弹出并停止,然后将临时栈的数据同样的手段push回到max stack。 这么做的原因是:之前min stack的方法里面,只考虑了元素相对于之前压栈元素的最大值关系(替补值只是到最大值那个位置的替补,而不是整体的最大值的替补),而不考虑之后的,在有删除最大值操作的时候,最大值删除后,该元素之前和之后的元素都会被影响到,之前的元素可以不用新加考虑,而之后的元素需要这种倒腾的手段来原样处理,之后的元素完全可能作为新的最大值。

也就是说,临时栈还原到max stack的时候,由于还原的值有可能大于新的最大值的替补,使用和之前push操作相同方式进行还原,最大值是可能发生变化的。 minStack里面,压入的值只要小于等于最小值,就需要替补值。注意等于的时候也要放入替补值。

PS. 遇到等于之前的最大值,也需要创建替补值,因为弹出时候,只看栈顶等不等于最大值,如果不处理,那么相等不代表是最大值。

84. Largest Rectangle in Histogram

题意:直方图里面求最大矩形的面积。

:此题其实是数学题,数学的本质就是对于一个曲线求最大内切矩形面积:解法就是先列内切方程,然后解方程求最大值所在。只不过此题是离散的,用编程来解,其实就是一个一个值去计算,然后比较看哪个比较大。

首先看如何暴力求解。整体思路是对于每个柱子,我们单独用O(n)时间求解相对于它为高的最大矩形,然后比较所有结果哪个大。整体时间复杂度是O(n^2)。

对于每个元素的考虑它的最大矩形举例:对于下图高度5,最大矩形面积就是5*2。理解:元素乘多少要看它两侧第一个低于它的元素。在举个例子:对于下图第二个元素2,它的最大矩形为2*4,原因就是左侧第一个比它矮的是1,右侧第一个比它矮的为边界,边界到左侧第一个元素的距离就是4。 可以优化为O(n)的解法。关键是使用单调栈。单调栈的作用就是可以O(1)时间找到每个元素左右最近的第一个比他大或者小的元素。对于第一个2,它的左侧第一个比它小的元素不存在,因此是边界,即为-1,也就是栈为空的情况,扫描到1的时候,栈顶的2发现右侧第一个比它小的元素就是1,因此开始计算自己:自己的高度 乘以(1的下标 减去 左侧的边界下标-1 减去 1),计算完自己后,就可以出栈了,在把1压栈,扫描5,发现5比栈顶大,也就是说5的左侧第一个比其小的元素就是栈顶,但是右边比它小的目前还不知道,因此压栈。这样我们就知道程序该怎么写了,如果一个元素比栈顶小,那么说明栈顶右侧第一个比其小的元素找到了,而且左侧比其小的就是栈里面的它的前一个元素,所以栈顶可以计算了,反之,就还是压栈。 边界情况:如果当前扫描元素等于栈顶,那么当作栈顶右边找到了,因此计算栈顶,之后把当前扫描元素压栈。

PS.为什么左右两侧第一个较小元素就能决定最大矩形的另一个数学理解:如果遇到两个波峰,例如上图中的6和3是两个波峰,我们可以把第一个波峰削掉,也就是拆分成两个部分去考虑,维持第二个波峰的单调性。也就是,对于1,5,6,2,3,我们在5,6两个柱子的2高度上削一刀,然后1,2,2,2,3作为一个部分考虑,然后5,6两个柱子作为一部分考虑。从数学上看,最大内切矩形只能在这两部分之间产生。

85. Maximal Rectangle

题意:找出0,1二维矩阵中的最大面积的矩形。

:此题是84题的follow up。对每一行考虑,每行以及以上的行作为直方图来看,连续向上的1当作柱子来看。

636. Exclusive Time of Functions

题意:函数之间相互调用,调用另一个函数后,时间算另一个函数的。现在给出(函数id:开始或结束:时间点)三元组,求所有函数时间消耗。

:此题如果只是从头到尾去扫描,那么之前的信息会丢失掉,不可行。

此题最好使用的数据结构就是栈,可以模拟函数调用,就把函数id入栈,遇到函数结束,那么出栈,并计算时间。栈顶就意味着当前正在工作的函数。

设置prevTime记录上一个log记录的时间,扫描每个log记录,与当前栈顶进行比较,如果是end记录,那么说明栈顶函数要结束了,该函数的时间累加上end的时间减去prevTime再加1,例如函数1从第2秒开始,到第5秒结束,我们认为他执行了2,3,4,5总共4秒,之后当前函数出栈。 如果不是当前函数,那么说明是启动了一个新函数(假设为函数2)打断之前的函数(假设为函数1),那么先将新函数压栈,然后计算之前函数的在此被打断之前执行了多少时间,就是当前时间减去prevTime,理解:如果上一个log是start,那么是新开了一个函数的情况,例如上一个log时间是5,当前函数2从6开始,说明第6秒时已经切换,所以执行了1秒。如果上一个log时间为end时间,那么之前函数是结束了,当前打断的函数其实是栈顶函数,栈顶函数只计算从上一个函数结束为止到当前时间,也等于当前时间减去prevTime。 PS.c++可以使用istringstream或者find_last_of来切割字符串。 总之,对新的log的状态,对栈顶函数进行时间新增计算,记录pre log的时间。

388. Longest Absolute File Path

题意:给出目录,求出最长文件路径,所谓最长是指含有的字符最多,而不是指文件夹层数最多。

:此题难点在于不知道使用什么样的数据结构来有效地解决问题。

大致思路就是文件夹是树结构,沿着文件夹树目录模拟一层层打开文件夹找文件的过程,沿途记录下走过的路径的长度,一旦找到文件(叶子),我们记录下到达此文件的路径长度,当所有文件被找出来的时候,我们就能知道最长的是哪个。

注意的是,存在一个文件夹下有多个文件夹的情况,所以存在找到文件后退到上一层继续计算的情况。

合适的数据结构一种就是栈,栈记录到达当前层的长度,那么栈的深度代表了当前层数,如果需要返回上一层文件夹,只需要进行弹栈操作。另外也可以使用hashmap来记录层与长度的对应关系,原因是此题是字符串处理,只需要一行行的分析,自然就可以模拟文件打开过程,所以不一定要使用栈。

接下来就是编码,对于c++,使用流来处理字符串,将每一行切割出来,然后看每一行的’\t’数量,也就是看最后一个’\t’所在下标减0就是’\t’数量。\t’数量代表了当前层的深度,因此,在发现栈的深度大于当前层的深度的时候,说明要弹栈了。

另外,c++使用find_last_of(’\t’)来寻找最后一个’\t’所在下标,如果不存在,那么返回-1。 PS. 1.由于计算当前层长度需要知道之前一步的总长度,所以先压入0到栈中,保证栈一定不可能为空。

2.编程的时候,弹到当前时候,可以选择弹到上层,然后重新进入当前层。

3.使用hashmap有一个好处,就是完全不需要弹栈,每次只需要根据上一层和当前层的值修改当前层即可。

4.路径中的“/”也算一个长度,所以在除最后一层外的层都要多加1。

503. Next Greater Element II

题意:找出数组中下一个比当前元素大的值(如果不存在,那么使用-1作为结果),数组可以循环。

:此题是典型的数组可以从头开始循环的问题。解法也就是套路中的将数组当作两倍数组来看,后面放一个一模一样的数组。

接下来就是寻找每个元素下一个最大元素的问题,如果对每个元素,扫描后面元素,这样时间复杂度是O(n^2),不符合要求。

优化是使用单调栈的技巧,求下一个第一个比自己大的元素,就是看右侧最大邻居。

331. Verify Preorder Serialization of a Binary Tree

题意:验证先序序列化序列的是不是合法的,例如给出“9,3,4,#,#,1,#,#,2,#,6,#,#”,其中#代表空结点。

: 方法一:可以使用stack来模拟先序遍历。遇到非空结点,直接入栈;遇到空节点则是先看栈顶是否是空结点,如果是,那么连续两次弹栈(弹出空结点和对应的叶子结点),如果栈顶不是空节点且栈不为空,那么直接压栈。

连续两次弹栈过程中如果栈出现空或者栈本来就为空,则直接返回false。栈顶不为空弹出时候,要将一个空入栈,代表该结点是处理过的,已经被置空了。

最终的栈是一个空节点,其他情况不合法。

方法二:每加入一个非空结点,非空结点先消耗掉一个入度,即树的总入度先减1, 然后非空结点带来两个2个新入度。每加入一个空节点,空结点先消耗掉一个入度不带来新入度,所以总入度减1。如果扫描序列过程中出现总入度是负数,或者最终结果是总入度不等于0,那么不合法。注意,一开始时候总入度是1。

373. Find K Pairs with Smallest Sums

题意:给出两个已经排序的整数数组,给出一个整数k,求出两个数组组合出的pair(x, y)里面x + y最小的k个(x,y分别来自两个数组)。

:如果暴力求解,那么是O(m*n)。如果加上已排序信息,修改此题的解空间,发现和k路归并非常类似:给出k个升序的list,如何知道当前最小的数呢?只需要比较所有list的第一个可用元素。取出最小的即可。而且,不需要提前知道所有的和,看结构就可以了。时间复杂度O(k * logmin{m, n})。

使用优先级队列,取数的步骤如下:

首先,选nums2的第0个元素,搭配k个nums1中下标0到k-1的元素(如果不足k个,那就全放入),然后我们知道第一个最小pair一定可以从这些数中产生,而且最小的k个pair一定比这些pair小,也就是说,如果nums1的size比k大,那么nums1中下标k-1之后的元素也不需要考虑了。

然后,考虑每次怎么更新,也就是根据弹出的最小值把对应的下一个候选pair构造出来继续入队列。上图中,step2弹出来的是(7,2),下一个入队列的是(7,9)。规律就是第一个元素不变,第二个元素变为nums2的下一个元素。这么做的原理是什么呢?为什么不加入(11, 2)呢?这是因为11与2的组合,我们曾考虑过了。为什么第三步弹出(1,9)后选择(1,10),而不是选择(7,9)呢?因为(7,9)也考虑过了,那么为什么都考虑过了呢?

画一个二维矩阵就明白了,1,7,11,16作为横坐标,2,9,10,15作为纵坐标,那么首先把第一列的和算出来,然后从中选择最小的,取出,然后放入纵坐标加1的,横坐标不变的元素,因为我们知道,当前最小值一定是从每行最新头里面出,就是其中最小的那个。

此题类似于super ugly number题,也就是每个新生成的最值会对下一个候选者产生影响,而候选者往往是从几个数里面挑出来。通常解法就是优先级队列,一开始放入所有候选队列的队列头,然后每次取出来一个最值,然后更新候选队列的头。

实现的时候记录下每个pair的nums2元素所在的下标,然后每次下标加1取出下一个nums2元素。

659. Split Array into Consecutive Subsequences

题意:给出有序序列,现在要把其中的连续(相差1)序列拿出来,如果拆出来的序列都是长度大于3,那么返回true,否则返回false。

:每个元素i,要么接入i-1为结尾的序列中,要么自己作为头。根据升序来扫描,如果每个元素都能最终接入到长度大于3的有序序列中,就返回true。例如:123345,如果拆成1234和35,那么就不满足条件,所以,在4面临123和3这两个序列时候,应当加入短的那个3,而不能加入长的123。

方法一:优先级队列+贪心。设置map<int, pq> 来表示以数字i结尾的所有序列存到优先级队列中,堆顶就是长度最小的那个序列。

每次遍历数字i,如果i-1对应的pq不为空,那么将堆顶摘下一个元素(是以i-1为结尾的序列的最小长度),存到数字i对应的pq中。最终遍历一遍所有pq,如果没有长度小于3的,那么说明是true。 时间复杂度为O(nlogn)。

方法二:思路与之前一样,但是这次不使用pq,不使用的原理是该方法保证了对每个数字做判断的时候都保证其存入的序列长度比3大。具体操作:先把每种数字对应的数量存到freq表,然后遍历的时候使用tail表来记录以i为结尾的序列个数,这些序列要保证比3长。如何做到比3长呢?每次处理数字i的时候,如果存在i - 1结尾的序列,那么将i - 1结尾的序列个数减1,然后以i结尾序列个数加1,如果不存在i-1结尾的序列,那么看freq表中是否还有多余的i+1和i+2,如果都有多余,那么将i+1和i+2取出来,直接让以i+2结尾的序列数加1,如果都不行,那么就返回false表示此数无法凑成3个以上的序列。

方法二将时间复杂度降到O(n)。

402. Remove K Digits

题意:给出数字串,然后给出删除的次数限制k,求删除后得到的最小的数字串大小。数字的次序不发生变化。

: 此题一开始想到的是dfs,dfs需要对每个数字考虑是否删除,然后继续向下一层搜索,花费的时间是n个数字中选k个的组合数,k大约为3的时候,时间复杂度几乎为O(n^3)。这样时间复杂度太高。

显然此题是找规律的题目,而且此题的规律就是贪心法,尝试构建串,从左到右考虑把数字加入新串,如果当前数字比新串结尾数字小,说明可以选择当前数字来替换掉之前数字。如果是12345678,k=4,那么答案就是1234。如果是123451,k=1,那么答案是12341, k=2,那么答案是1231, k=3…。

规律就是:越靠左边的高位值要尽可能小,在保证顺序不变的前提下,也就是在发现可以更新左边位置数的时候替换左边位置上的数,同时考虑删除有限制次数。

还是使用单调栈来解题:从左到右选择递增的值加入最新的结尾,如果出现递减的情况,那么将在考虑删除次数限制的情况下,将单调栈里面能更新的数全部删除,之后加入最新值。

得出结果后,还要注意边界情况,一个是结果是空的,或者结果是0开头的串,以及结果串大于所要求的res的长度。空的时候说明全部可以删除,所以答案是’0’,结果是0开头的串,要把之前的0删除掉。串大于结果长度时候,先要resize,只保留升序的前面部分。

330. Patching Array

题意: 给出有序的数字数组nums,然后给出一个n代表1到n的区间,由nums中元素的组合的和等于区间内一个数字,现在要保证和能覆盖1到n,求缺失的最小数字为几个。

:此题使用贪心法。设置miss变量代表变量数组nums过程中缺失的最小数字。

例如:nums = {1,2,4,13, 43}, n = 100。一开始miss candidate等于1,发现和第一个元素相等,所以1不是miss的,现在miss candidate变为2 (miss candidate + nums[0]), 发现2 == 2仍然存在,那么miss变为 4 (mc + nums[1])。4 == 4,说明4不是miss的,然后miss变为 8 (mc + nums[2]),发现8 < 13, 8是miss,因为13不能和任何的1到7配合来生成8,相反,假设不是13,而是5到7,例如7 < 8,那么7可以和之前的1来配合生成8,8就不是missing。

此时只有13,所以添加8作为missing,结果加1。下一个可能的miss变为 16(miss + miss),因为8之前的数字1到7都可以构造,而8是新添加的,然后 16 < 13 (缺失的时候i并不++),16并不是缺失的元素,因为当前13可以配合之前的1到15形成1到29的数,所以下一个缺失的数变为 30 (miss + nums[i]),一直到扫描结束,就可以得出最少的添加数字。扫描并不是对数组元素而是对整个区间n,如果数组到最后一个数字,那么将是miss自己的double了,不用考虑数组里面的元素了。

其中,为什么只考虑mc + num[i],而不用考虑mc + 1到miss + num[i]之间的数?因为mc是最后一个不miss的数,意味着1到mc全部不miss,而这些可以用来构造mc + 1到miss + num[i]之间的数。例如对于4,4和3可以构造7,4和2可以构造6,4和1可以构造5。

394. Decode String

题意:s = “3[a]2[bc]”, return “aaabcbc”.给出压缩串,还原。

:此题是栈,但是操作过程中,还是很有难度。先分为数字栈和字母栈,遇到“[”的时候,意味着新的扩展层的开始,所以使用temp变量,遇到“[”的时候,temp就清零(把之前的temp存入字母栈)。遇到“]”的时候,需要把之前temp从字母栈顶拿出来并扩展数字栈顶的倍数,然后弹出字母栈顶。

理解:模拟函数递归返回过程,栈顶实际上就是内部子函数的临时返回结果,然后每次这个返回结果被上一层处理,返回给上上层。如果两个函数是同一层级的,那么进入新函数的时候(遇到“[”的时候),会把当前函数层的临时值置为空,也就是说只有当前函数层的临时值才会被翻倍。

321. Create Maximum Number

题意:给出两个数字数组,现在求从两个数组一共取出k(k小于等于数字数组长度之和)个数字组成数,求最大能组成的数,要求是数字要维持原数组中的顺序。例如: nums1 = [3, 4, 6, 5]

nums2 = [9, 1, 2, 5, 8, 3]

k = 5

return [9, 8, 6, 5, 3] :这个问题可以分解为两个问题: 第一个是问从一个nums数组中保持顺序取出i个数字能组成的最大数为多少。

解法是:例如[9, 1, 2, 5, 8, 3],那么i = 2,我们发现98最大,如果i == 3,那么983最大。所以找最大数要使用单调栈,扫描一遍数组,保持一个需要丢弃的总数,当前扫描数如果比栈顶大,那么看丢弃数是不是> 0,如果是那么尽可能的丢弃比当前小的值,否则直接入栈,然后取出栈的前i位就能组成最大数字。

第二个是问从第一个数组里面取出i个数,从第二个数组里面取出k - i个元素能够组成的k位数中最大的那个。

解法是尝试i从0到k的各种取法,然后比较结果值哪个大就可以了。里面的小细节就是把两个取出的数字进行合并。合并的方法就是双指针,一个指针指向第一个数开头数字,第二个指针指向第二个数开头数字,每次向最终数字的最高位放入其中比较大的数字。这样既能保证数字在数本身中的顺序不变,又能够求出最大合并数。

PS. 1.从m和n中选k个的情况不好分析,假设m < k,那么nums1就可以从0选到m,如果m > k,那么nums1就不是简单的从0选到k了,假设选0,那么万一 0 + n < k,也就是说,nums2没有足够的元素来组成k,所以m > k的时候,应该至少从nums1中选k - n个数字,也就是说是从n - k到k。

2.合并数的时候,如果数字相等,那么要看两个数组下一个位置,从其中较大的数组中选。

224. Basic Calculator

题意:实现带括号、正数的加减(没有乘除)的计算器。

:先考虑不带括号怎么计算,不带括号的难点在于减法,技巧是减法等于加上负数,变为负数难在先遇到减号,然后在遇到数字,所以需要使用全局变量记录当前环境是加号还是减号,当前数字处理完之后就乘以当前环境的符号。

在考虑带括号,技巧就是把括号括起来的看作子函数进行处理,在遇到左括号后,单独启动一个循环,找到它对应的右括号,然后当作子函数处理即可。

PS. 函数的实现本质还是使用栈模拟保存调用函数时候的返回值。遇到左括号的时候,说明新函数开始了,所以要先把调用函数的当前计算值压栈保存,然后还原临时变量给下一层来使用。遇到右括号的时候,说明当前函数结束,那么把当前计算结果与从栈中弹出的结果相结合,相当于返回上一层,也就是还原上一层函数的环境(临时变量)。

方法二:使用符号栈和数字栈,符号栈其实是一个单调栈。详细分析见772题。

227. Basic Calculator II

题意:此题是实现不带括号的加减乘除计算器。

:此题难点在于扫描遇到乘除符号时候,只知道之前计算的值,并不知道之后num的大小。

方法一:把符号保存下来,遇到数的时候,在根据符号来处理。其中,加减是把串进行分割的关键(因为加减的优先级包含的部分是独立一部分),遇到加减,临时值就可以清零了。

例如,这么理解“+2*3”:遇到+的时候,是把当前符号变成+,然后遇到2,把2结合当前符号,也就是正2保存到临时结果,然后遇到*的时候,把当前符号变为*,然后遇到3,由于是乘,所以和之前值进行相乘。如果3后面是乘除,那么继续操作,如果是加减,那么之前的临时值要加入最后结果,然后清空。

注意的是:这种解法思路是先发现数,然后遇到符号进行处理,但是其中还有一个隐含的边界处理,那就是扫描到末尾的时候,也需要把临时值加入最终的结果里面去。

方法二:使用符号栈和数字栈,符号栈其实是一个单调栈。详细分析见772题。

推荐方法二。

772. Basic Calculator III

题意:227基础上,带括号。

:计算器问题本质是先扫描到的串不一定先计算,里面蕴含了优先级,优先级的计算顺序看起来是混沌的,仔细想想,数学上应该是找曲线的波峰,然后把曲线变低平的过程。

方法一:227基础上,把括号内的当作子问题处理。

方法二:使用符号单调栈。栈里面保存的是递增优先级的符号,如果当前符号的优先级比符号栈顶的小或者等于(或者扫描结束),意味着栈顶的符号是波峰(局部的最高点),可以直接计算了,因为他对左右两边的数的影响是时间上优先级更高。如果遇到右括号,说明栈里面最上面的左括号和当前右括号之间是递增的关系,里面可以作为一个局部的高曲线,可以全部拿出来计算。

PS.加减乘除的模型就是每个符号都要对两侧的数字产生影响,那么符号如何影响呢?

考虑1+2+3和1+2-3,对于第一个+号,我们知道,它可以先进行计算;再来看1+2*3和1+2/3,第一个+就不能先计算了。原因就在于在表达式的右侧,如果存在一个不比+优先级高的符号,那么可以先算,否则,+只能先存起来(例如存到符号栈里面),之后在进行计算了,把计算的优先级给后面更高的算符。右括号是优先级最高的,需要先把包含在括号里面的算符先算完。

如果把符号比做链接左右的点,那么高优先级的符号就是波峰的点,应该优先计算这样的点,使得整个的曲线越来越低平。括号里面的内容是一群单调上升的点,应该从高到低依次计算。

581. Shortest Unsorted Continuous Subarray

题意:给出一个整数数组,求里面最大的子数组旋转后,使得整个数组是升序的。返回子数组的长度(也可以求出下标的pair)。

:此题暴力解法就是先排序,然后从左右向中间比较第一个不相等的元素。时间复杂度是O(nlogn)。可以进一步优化为O(n)的解法:思路就是不排序就找到第一个违反规律的元素。方法是单调栈,从左到右扫一遍找到最左边违反规律的元素,从右向左扫一遍找最右边违反规律的元素。

从左向右扫描,使用单调栈保持递增序列,如果扫描元素比栈顶大,说明栈顶违反了有序,这样要弹栈,把所有违规的都弹出来,并记录下最靠左的违反元素的下标。

同理处理从右向左的扫描。

小结:单调栈可以O(N)时间得知数组里每个元素是否存在右边比他大(小)的元素。

862. Shortest Subarray with Sum at Least K

题意:求子数组subarr中,和大于K(K大于0)中的长度最短的那个。subarr中含有负数。

:一开始以为是双指针题目,然后发现暴力求解根本无法使用双指针优化,因为其中包含负数。然后考虑是不是动态规划,发现子问题之间似乎没有明显的联系。

无论如何,首先是一定要使用presum技巧的,计算presum使用n时间,presum数组的第一个元素默认为(0, 0),然后每个元素num[i]在之前处理的presum里面找出num[i] - num[j] >= K(j < i)的,扫描之后最小值就得出来,这样总体花费的时间是O(n^2),不理想。

考虑将之前计算的presum记录为pair,一个记录是presum大小,另一个是下标。如果按presum大小进行排序,或者说放在set里面,也是不理想的,这样时间复杂度还是降不下来。因为即使快速的知道了有几个子数组符合要求,但是也需要对每一个子数组都拿出下标来计算子数组的长度。

如果能进一步利用下标的信息,就可以将复杂度降低。技巧是使用带时效的单调栈,也就是Deque,之前计算window里面的max的题目中就使用了deque。

本题的deque特点就是:Deque中元素从左到右(左侧为front,右侧为back)一定下标递增,因为每次从deque的右侧压入元素;Deque中元素从左到右大小递增,这个性质需要维持。

边扫描边更新Deque。对于当前正在扫描的元素,Deque中的元素对于它来说的意义是作为搭档,为最终最优解提供候选解。 ii 先看deque的最左端元素(设为y)结合当前元素对最终最优解的影响:如果当前元素减去这个元素已经大于等于K了,那么可以作为候选者之一,但是可想而知,下一个即将的扫描元素,即使减去这个y,得出的下标跨度只会更大,不可能作为候选者,也就是说,y不会对于之后的扫描过程做出任何的贡献了,因此可以从front弹出。

再看deque的最右端元素(设为z)结合当前元素cur对最终最优解的影响:首先z的序号比cur小(Deque中序号递增),如果z的值也比cur值小,那么可想可知,对于下一个即将的扫描元素,如果减去cur值大于等于K,那么一定也可以减去z值大于等于k,且基于cur的跨度一定小于基于z的,因此z不会对之后的扫描过程做出任何的贡献,因此可以从back弹出。

注意:由于当前元素cur没有被之后的元素考虑,因此当前元素每次都是必须无条件入deque的,以便之后的扫描元素参考。

因为每个元素只会入deque一次和可能出一次,每次进出的时间消耗都是O(1),所有元素扫描处理一次就能得知答案,所以总时间复杂度是O(N)。

总结:此题模型是寻找一个数组里面两个元素相减大于等于K,且两个元素之间距离最短的那个。

K大于0或者小于0,其实是不重要的,只不过从右到左考虑的时候,判断条件变为p[x] - p[y] <= K。

带时效的单调栈这种技巧可以解决的问题的特点是:求最值,最值被两个维度的信息所影响,且其中一个维度和下标有关,这样,通过单调栈保持下标递增的情况下,从栈的两端进行考虑,例如从左到右,把将来不会对最优值做贡献的元素去掉,然后从右向左做同样的考虑。

857. Minimum Cost to Hire K Workers

题意:N个workers选出K个,保证总工资最小。其中工资w要和打分q成正比,每个worker的工资要大于每个worker的期望。

:先考虑全选的情况,全选的时候,根据数学知识,知道,一定会选择对每一份平均期望工资w/q最大的那个来发。理解:可以先尝试按照每个人的最低期望工资来发,发现根据比例,有些人是发不到他的期望工资的,为了达到这个人的期望工资,会将当前选择的基点成倍提高直到超过这个人的期望,这样算下来,由于比例是固定的,所以总额一定比直接按最高平均期望的工资多。

再来考虑只选择K个的情况。现在问题变成,需要从n个(q, w)的pair里面选出k个,让总工资(w总和)最少。 知道选出的K个人里面,q的总和越小越好,w/q的最大值越大越好,首先暴力解时间(从n个里面强制选K个,然后计算比较)复杂度太高。

此题应该有简单解。发现问题就是想选择K个pair,这些pair的特点就是其中最大的w/q作为基准的,那么可以从第k大的w/q开始考虑,但是除了第k大项以外,从第k+1项开始还是不知道具体要选哪k个。

解决方法是使用优先级队列来解,首先将w/q按小到大排序。然后队列放入k个元素,这样恰好里面最大的w/q也就是第k大的Wk/Qk。 然后需要做的就是尝试放入第k+1大的Wk+1/Qk+1,首先,知道此时一定是按照此Wk+1/Qk+1计算,其次,要考虑是如果替换队列里面的一个元素,总体是不是更优。方法就是,把其中q最大的放在堆顶,这样可以每次都把最大的分数给弹出来,也就是替换分最大的结点。

细节:先把0到k-1的q总和求出来,对于第k个,使用w/q作为基准来计算总工资,从第k+1开始,使用当前的w/q,使用自己的分数取代之前的栈顶分数,如果计算处的总工资比之前的总工资最小值要小,那么就把之前的最大分数弹出来,把当前元素压栈。

有的时候会出现当前计算的总工资和之前计算的总工资相等的情况,此时不能将之前的栈顶弹出,因为这样计算出来的总工资候选值,虽然总工资相等,但是w/q大,所以总分数小,而之前总分数越大时候,后面更大w/q基点计算的时候,可下降的幅度就越大。

也可以进一步优化:也就是不考虑当前计算的总工资要不要使得栈顶替换,而是每次栈长度大于K的时候,立即弹出,每次必把当前基点入栈。 这样是正确的原因是:考虑了所有的候选者,且每个候选者都是根据相对于自己w/q的最低总分数来计算的。

855、ExamRoom

题意:0到N-1表示连续座位的下标,现在人有坐和离开两种操作,坐的时候要满足离身边的人最远(如果相等,那么选座位号码小的),离开操作题目保证一定可以是有效的位置。要求设计坐和离开两种操作。

:此题是区间题,知识点是对pair的优先级队列如何写,如何使用treeSet来处理pair,以及如何定义区间。

我们知道,坐操作的时候,选了点之后,会以自己为分割点分割座位。关键是定义区间:把区间[a,b]定义为从a开始到b有连续的空座位,包括端点。区间只不过是我们快速记录连续空位的手段,减少存储空间,而不是问题的本质。

区间[2,4]究竟意味着什么?意味着:(1)2,3,4是空座位; (2)1,5被人占了。(3)如果新来的人选区间[2,4],那么,他一定只能坐3号座位,且区间[2,4]不在继续存在,而是变为了两个新区间:[2,2]和[4,4]。

在看[2,2]意味着什么?答案是:(1)1,3被占了;(2)选该区间的话,只能坐2号位置;(3)该区间将消失。

在看[2,3]意味着什么。(1)1,4被占;(2)选2号位置,因为同样距离选小的号码(3)选择后,该区间消失,变为[3,3]

再来看离开座位怎么恢复区间:例如有7个位置,0,1,3,6被占,可知此时区间信息为[2,2][4,5]。假设此时3离开位置。

那么可以知道,可以将2位置的左边进行扩充,可以将4位置的右边进行扩充。也就是说,需要找到以2为右端点的区间以及以4为左端点的区间。如果找不到,那么2,4被占,也就是说,此时3将作为新区间的左端点或者右端点。

最后再来看初始化情况,也是最难考虑的之一:一开始的时候,例如7个位置,[0,6]区间的情况下,第一次插入的位置并不能是2,而是应该是端点0,插入后的区间变为[1,6],而第二次插入的时候,应该选6,而不是3。这种情况出现的原因就是,区间包含了开头和结尾。因此这种情况要进行额外处理。

还有一个易错点:区间[1,3]和区间[5,8],看起来[5,8]区间更大,其实选座位的时候,两个区间是等价的,也就是说,座位2和座位6都是最远是距离1。还有就是,区间[0,2]和区间[4,7],包含端点的情况下,[4,7]的优先级更高。

PS.优先级队列的opeator里面大于小于的理解:只有为true的时候,才把两个point挪位置,也就是说,把p2挪到p1的前面表示优先级更高。

856. Score of Parentheses

题意:()作为1分,被嵌套后翻倍,求给出的括号序列的分数(给出的括号是平衡的)

:一种思路是使用栈,遇到左括号,压栈,意味着进入了一层新的函数,然后,遇到右括号,意味着当前函数要结束了,结果要返回给上一层处理。

那么,是什么样的函数呢?一开始定义一个res为0,然后,计算下一层,并将下一层的结果翻倍,然后返回。

遇到左括号,也就是遇到新函数时候的处理:将之前的计算的局部res值压栈,res置为0表示新函数的开始。

遇到右括号,也就是函数结束的时候,把当前计算的res*2(如果res是0,说明是()的函数,返回1)加到上一层局部res中。

另一种思路:遇到左括号,意味着层数加1,遇到右括号,意味着层数减1,如果遇到(),那么看()当前是第几层,假如是第i层,那么它对最终结果的贡献就是2^i。

973. K Closest Points to Origin

题意:给出二维点的数组,求其中最接近原点的K个点。

:此题解法多样:

方法一:耗费时间O(NlogN)。就是把所有元素进行距离原点大小排序,选最小的K个。

方法二:耗费时间O(NlogK)。也就是经典的使用K大小的优先级队列,使用大堆。

方法三:耗费期望时间O(N)。也就是经典的快速排序算法中的quickSelect技巧。quickSelect每次选一个pivot,

把数组变成左边比pivot小,右边比pivot大的情况,然后对子问题进行递归。

这个算法的缺点是,比第K个小的所有元素并不是有序的。

735. Asteroid Collision

题意:行星碰撞。给出整数数组,元素代表行星的大小和移动方向(正表示向右、负表示向左),行星移动速度相同。

如果大行星撞到小行星,那么小行星保证,大行星保留,如果质量一样大,那么都消失。 现在求数组的最终状态。

:扫描数组,首先,如果遇到的数是负数,看之前的一个数,如果是正数,那么检查碰撞情况;如果是负数,那么这个行星目前不会爆炸,因为它的左侧没有行星能和它碰撞;

如果遇到正数,那么也是看之前的数,如果之前的数为正数,那么这个数暂时也不会有爆炸可能,如果之前的是负数,那么也不会爆炸。

其中只有负数遇到之前正数时候会进行碰撞检查,也就是从最后一个元素开始,如果值比负数绝对值小,那么直接删除,直到不小、遇到负数或者空为止。

编程技巧:使用vector模拟栈,在碰撞时候,如果之前元素被摧毁,当前元素保留,可以使用i–的技巧重新考虑当前数。

1249. Minimum Remove to Make Valid Parentheses

题意:字符串S,求删除最少的左右括号得到的任意一种合法字符串。

:此题和301题相似,但是不需要求出所有Valid Parentheses变体。使用301的BFS解法是会超时的。因为此题要深刻挖掘使用括号匹配的特殊规律。

这个规律就是:要删除的左右括号,其实就是在括号匹配过程中剩余的,具体来说:左括号的剩余情况就是,

这个左括号右侧的右括号全部已经被匹配了;右括号的剩余情况就是:右括号的左侧的左括号全部已经被匹配了。

可以知道:左括号是否剩余,必须等到整个匹配过程结束才知道,而右括号是否剩余,在匹配过程中就知道。

因此,方法就是括号匹配,使用栈记录尚未被匹配的左括号的下标,如果发现右括号,那么将最近的左括号的下标(匹配上了),也就是栈顶进行删除;

如果栈为空,说明左侧的左括号全部已经被匹配了,此时将要删除的右括号位置记录下来。

最终栈中剩余的就是剩余的左括号下标位置。

最终删除所有剩余的左右括号,得出最终结果,