所有代码详见：https://github.com/jingminglake/Leetcode
总体思路
关于序列中最大最小值的问题常使用的数据结构：
- 优先级队列
堆（优先级队列），耗时O(logn)插入元素，O(1)时间读取最小（大）值（堆顶），O(logn)时间删除堆顶。
PS.（1）堆和优先级队列的关系：堆是一种具体的数据结构，他的实现可以是数组、链表或者其它，但是从逻辑上来看，二叉堆就是一个完全二叉树。优先级队列是一种抽象数据结构，支持查找，插入和删除元素，不过，删除和查找元素的操作都是只能访问堆中的优先级最大（或最小）的元素。
也就是说，堆是实现优先级队列的一种方式（其他方式例如可以用平衡二叉搜索树来实现），而且是很好的一种方式（所有操作的时间复杂度均为O（logn））。堆和优先级队列关注的点不一样，前者关注一个二叉堆的性质，后者关注的是某种队列的性质。实际上二者基本是一种东西：解决的问题一样，只不过堆的结构更加具体。
（2）优先级队列找第k大
几种思路：第一种是把所有n个元素放入大顶堆，然后弹出n－k＋1个不符合要求的元素（比第k大的元素），这样堆顶就是符合要求的元素；第二种是把所有n个元素放入小顶堆，然后弹出第k个元素，就是答案；
这两种思路的坏处在于，时间、空间复杂度过大，例如n很大，而k比较小。第三种方式时间复杂度不变的情况下，只需花费O（k）的空间, O(nlogk)的时间。
第三种是维持一个大小为k的小顶堆，先随便放入k个元素，之后元素一个个的加入堆，
每加入一个，堆的大小是k + 1，其中堆顶的元素最小，且我们知道这个元素比k个元素小，因此做不成第k大，把它弹出栈。最终堆里面有k个元素，且堆顶最小，就是第k大。
所以，解题时候一定要使用第三种思路，这样，在k很小（10以内的题目都非常适用）的情况下，时间接近是线性的。
- min-queue
使用[min-queue](http://micili.cn/suan-fa-yu-shu-ju-jie-gou/2017-01-23)，耗时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
题意：给出一个数组，数组里面有一个滑动窗口，窗口大小为k，每次移动一个位置，要求每次取出滑动窗口中最大值，结果是一个序列。
解：此题如果使用multiset，时间复杂度是O(nlogk)。
O(n)的解法：使用双端队列。双端队列同时维持三种性质：第一种是单调性质：递减；第二种是下标递增；第三种是保证队列中的下标是合法的（也就是在窗口内的）。这样我们知道，双端队列的左端就是当前滑动窗口的最大值。
关键是如何快速维护这两种性质：每次窗口滑动的时候，会有一个元素失效，以及有一个元素会新加入作为候选的最大值。
也就是说，窗口滑动的时候，先从队列左端往右看，如果一个值的下标失效了（落在窗口外），那么进行删除，直到找到第一个的有效的（之后的一定有效，因为下标递增性质），或者到空；
然后对新加入的元素，从队列右端往左侧一个个看，如果新元素比队列里一个元素大，那么说明右端这个元素现在不可能作为窗口中最大元素了，而且以后也不可能了（因为当前元素的生命周期比这个元素长），因此去除掉；
相反，如果它比新元素大，那么需要保留，直到右端比当前元素小或者队列为空。最后，无论如何都加入当前元素下标到队列右端，因为之前的最大值一旦失效，当前的这个值就可能作为新的最大值。
编码的时候，双端队列里面存的是数组的下标。
480. Sliding Window Median
题意：每次移动滑动窗口，并从窗口中取出中位数。
解：此题与295题相似，但是此题属于可以从源中删除过久数据的这个场景，因此更加实用。
如果采用C++实现，此题可以使用multiset来替换priority_queue，继续使用295解法。使用multiset之后，求最大的数的时候，也可以不存负数，而是使用–end()来取最大值。
此题流程是，在两堆元素数量大于窗口大小时先删去由于更新窗口落在外面的元素，使左右堆满足条件，例如(5,4)变为（5，3）或（4，4），其中（5，3）需要调整；（5，5）可以变为（4，5）或者（5，4），其中（4，5）需要调整，调整之后其余按295题目方法来处理。
也可以只使用一个multiset，不过每次要使用库函数next来取得当前set中的某个迭代器的第n个后继。
如果采用Java实现，由于需要删除，所以可以考虑使用TreeSet数据结构，不过可惜的是Java的TreeSet不支持元素重复的这种情况。因此Java编码时候，使用TreeSet时候，存入的 元素不能是数据本身，而是要存数据的index。
一开始，前k个元素是没有median的，先放入treeSet里面，然后平衡，接下来每次都要计算一个median并平衡。平衡的意思是保证left比right最多多一个元素的性质，如果更多，那么left移动元素到right。 加元素的时候，先加到right，在从left移动first到right，这样也就是每次在left多加一个元素，这样就保证了平衡函数的可用性。
时间复杂度：O(nlogk)。
692. Top K Frequent Words
题意：输出前k频率的单词，单词如果频率相同，那么按字母排序。
解：使用优先级队列，队列大小严格控制为k，先随便放入k个单词，然后再把一个新单词加入队列，此时已经有k+1个单词了，
使用小顶堆， 那么堆顶单词已经比k个单词小了，不能进入前k，因此要弹出队列，因此。最后剩余的k个单词就是最大的k个单词。
这里的大，意思是单词出现的次数多，如果出现次数多，那么按单词的字典序小算优先级大。
PS.此题是很好的使用优先级队列的例子，很好的lambda使用语法形式。
https://github.com/jingminglake/Leetcode/blob/master/topKFrequentWords/topKFrequentWords.cpp
c++编码时候对于优先级队列比较运算符的心得：其实本质和vector是一样的，只不过pq的top相当于vector的最后一个元素，因此vector看起来是递增的，但是如果把vector当作队列，那么队列头其实是最大的元素，就是“最大堆”。
java编码：pq默认是小堆。
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)。 注意：尽量使用(1)。先看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（加入set）。
Java编码：由于Java的treeSet不支持元素重复，因此，很多答案使用优先级队列。但是使用优先级队列有个问题，删除指定元素的操作复杂度为n,而不是logn。 最好使用treeSet，方法是要处理重复元素，方法是，删除的时候，首先要知道删除元素的数量，如果是1，那么删除，否则，只删除一个，方法就是：treeMap.put(height[1], count-1);
PS. 1. 横坐标相同的时候，起始点排消失点前面。
- 二叉平衡搜索树顶点由于每次加入一个新元素带来的变化，可以用来动态的排序一组元素。
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
题意：直方图里面能形成的最大矩形的面积。
解：此题其实是数学题，直觉上，最大矩形面积一定是波峰的附近。实际上，可以使用暴力求解：
最后的答案一定在以某个柱子为高的矩形中，因此，对于每个柱子，往左右两边看，如果比自己高，那么继续（宽加1），否则停止，这样计算出以其为高的矩形面积，
举个例子：对于下图第二个元素2，它的最大矩形为2*4，原因就是左侧第一个比它矮的是1，右侧第一个比它矮的为边界，边界到左侧第一个元素的距离就是4。
花费O（n）时间。然后比较所有结果哪个大。整体时间复杂度是O（n^2）。
优化：实际上，我们只可以快速的知道每个柱子往左侧和往右侧比第一个比自己小的柱子。
方法是使用单调栈。从左向右扫描，栈维持递增（因为要和大数比较），如果一个数比当前栈顶元素大，那么栈顶将作为结果（最近最大）， 否则，栈顶元素不能要了，因为当前值比他小，后面的结果至少是当前值，因此弹出栈顶直到比当前元素小或栈为空。对于正在扫描的元素，如果比栈顶大，直接加入， 如果比栈顶小，栈会弹出比当前元素大的所有元素（直到栈为空），然后当前元素入栈。
神奇之处不止于此，从左向右扫描的过程中，由于单调栈是递增的，也就是说，如果当前元素比栈顶小，那么栈顶的右侧较小元素就是当前元素。
一遍扫描下来，每个元素的左侧和右侧较小值都知道了。
具体实例，对于第一个2，它的左侧第一个比它小的元素不存在，因此是边界，即为-1,也就是栈为空的情况，扫描到1的时候，栈顶的2发现右侧第一个比它小的元素就是1，因此开始计算自己：自己的高度 乘以（1的下标 减去 左侧的边界下标-1 减去 1），计算完自己后，就可以出栈了，在把1压栈，扫描5，发现5比栈顶大，也就是说5的左侧第一个比其小的元素就是栈顶，但是右边比它小的目前还不知道，因此压栈。这样我们就知道程序该怎么写了，如果一个元素比栈顶小，那么说明栈顶右侧第一个比其小的元素找到了，而且左侧比其小的就是栈里面的它的前一个元素，所以栈顶可以计算了，反之，就还是压栈。 边界情况：如果当前扫描元素等于栈顶，那么当作栈顶右边找到了，因此计算栈顶，之后把当前扫描元素压栈。
可以优化为O（n）。
PS. 单调栈的作用就是可以O（1）时间找到每个元素左右最近的第一个比他大或者小的元素。
85. Maximal Rectangle
题意：找出0，1二维矩阵中的最大面积的矩形。
解:此题是84题的follow up。对每一行考虑，每行以及以上的行作为直方图来看，连续向上的1当作柱子来看。
636. Exclusive Time of Functions
题意：函数之间相互调用，调用另一个函数后，时间算另一个函数的。现在给出(函数id：开始或结束：时间点)三元组，求每个函数自己消耗的总时间。
解：题意理解，有一点是，一个函数是可以在自己未结束的时候继续调用自己的，这也就是递归。但是就如括号匹配一样，只要一个函数起始结束满足括号匹配性质，那就是合法的。
所以最好使用的数据结构就是栈，可以模拟函数调用：遇到函数起始就把函数id入栈，遇到函数结束，那么出栈，并计算时间。栈里面的函数意味着当前正在工作的函数。那么此题看上去像是括号匹配，实际上确实如此： ({)}是括号匹配非法的，函数调用也是非法的，不存在栈顶是一个函数起始，但是当前扫描是另一个函数结束。括号匹配只解决了是否合法情况，此题需要考虑的是具体的入栈出栈。
这么考虑栈顶：如果当前扫描元素是end，且其必然和栈顶的id一样，那恰好弹出栈顶；如果当前扫描元素是start，那么栈顶的函数就是被挂起了，且当前元素必须入栈。
现在问题是：如何知道要被挂起的函数执行了多长时间呢？方法是需要记录它的开始运行时间：这个时间是它成为栈顶的时刻，因为成为栈顶意味着正在运行。
两种新栈顶出现的时刻：1. 压栈；2. 出栈（倒数第二个元素成为栈顶）。 无论如何，使用prevTime记录栈顶的元素它自己成为栈顶的时刻。
如果是end记录，那么栈顶函数要结束了，该函数的时间此次运行时间是end时间减去prevTime再加1，例如函数1从第2秒开始，到第5秒结束，我们认为他执行了2,3,4,5总共4秒，之后累加到该函数总时间上，然后进行出栈。
此时栈顶元素重新开始运行，也就是说，prevTime修改为当前元素的end时间 + 1（理解：结束的下一秒），表示新栈顶元素的重新开始运行时间。
如果是start记录，那么此时要挂起栈顶元素，先计算栈顶元素执行了多长时间， 就是当前函数start时间减去prevTime，理解：例如prevTime是5，当前时间是6，说明第6秒时已经切换，所以只执行了1秒。然后prevTime更新为当前函数start时间。
还要考虑一种特殊情况，也就是栈空的情况，栈空的时候，现在必然是start记录，需要压栈，此时只需要记录开始时间，也就是压栈元素的start时间。prevTime一开始初始化为0。
PS.c++可以使用istringstream或者find_last_of来切割字符串。 总之，对新的log的状态，对栈顶函数进行时间新增计算，记录pre log的时间。
388. Longest Absolute File Path
题意：给出一个字符串表示目录，原理是其中的\n表示换行，\t表示它所在的层数， 例如：dir ⟶ subdir1 ⟶ ⟶ file1.ext ⟶ ⟶ subsubdir1 ⟶ subdir2 ⟶ ⟶ subsubdir2 ⟶ ⟶ ⟶ file2.ext 其中的⟶就是tab，目录的字符串表示为”dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext”
现在要求出最长文件路径的长度大小，所谓最长是指含有的字符最多，而不是指文件夹层数最多。还有一定要注意，路径里面包含’/’表示层，’/’也算在总长度里。
解：此题难点在于给出的数据结构并不是常见的树结构：
文件夹在逻辑上是经典树结构，但此题数据结构并不是常用的树数据结构（结点，指针），所以无法进行经典dfs套路。要利用此题具体条件，扫描一遍，其实就是一种对树的遍历， 通过\t的数量，其实就知道树结点当前的所在层数(从0开始)，包含’.’的结点就是叶子。
难点是如何退回到上一层，也就是如何保留上一层的信息。
方法一：使用栈，栈记录到达当前层的长度，栈的深度代表了当前层数，如果发现当前层数比栈的大小大1，那么说明需要压栈，如果当前层数和栈大小一样， 那么说明栈顶需要更新，也就是出栈加压栈操作；如果当前层数比栈大小小，那么说明出现了跨层跳这种情况：从叶子直接跳回到根，或者是第四层跳到第二层这种，此时需要做的就是多次出栈，直到比当前层数小，然后把当前层的值加上栈顶的值压栈。 注意栈为空的特殊情况。可以加入0表示层数0，作为哨兵值dummy。
方法二：使用hashmap，方法是记录层与长度的对应关系。还是扫描一遍，遇到第一层的时候，记录下第一层的长度3，然后遇到第二层的时候，当前长度需要加上第一层的长度， 遇到第三层同理，不过如果第三层里面包含’.’，那么说明是叶子，此时结果作为候选值，之后，假如遇到第二层，那么更新第二层的长度为当前长度加第一层长度，因为之前的第二层信息已经不需要了。 这种思路比较难想。
接下来就是编码，对于c++，使用流来处理字符串，将每一行切割出来，然后看每一行的’\t’数量，也就是看最后一个’\t’所在下标减0就是’\t’数量。\t’数量代表了当前层的深度，因此，在发现栈的深度大于当前层的深度的时候，说明要弹栈了。
c++使用find_last_of(’\t’)来寻找最后一个’\t’所在下标，如果不存在，那么返回-1。 java使用lastIndexOf(“\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），现在求最小的k个x + y。
解：所有的pair组合是m*n个，如果全部求出，然后排序，那么时间复杂度将是O（m＊n * log(m*n)），也就是暴力求解的复杂度。
此题可以利用已排序信息：
实际上，此题和k路归并非常类似：k路归并中给出k个升序的list，如何知道当前最小的数呢？只需要比较所有list的第一个可用元素。取出最小的即可。
此题中最小的组合必然是两个第一个元素。注意结合使用优先级队列技巧。
方法一：维持一个k大小的优先级队列（小顶堆），取数的步骤如下：
第一步，先往优先级队列中放入k个候选最小值：
以nums2的第0个元素为基准，搭配k个nums1中下标0到k-1的元素（如果不足k个，那就全放入）；
第二步，得到最小的pair，并放入下一个候选者：
我们知道最小pair一定第一步的k个数中产生，使用最小堆，把堆顶弹出来就是最小值。
之后，弹出来的这个值的下一个下标做基准继续考虑，理解：
第一步得到的优先级队列中已经存在k个候选者，假如nums1下标k-1后仍有元素，那么它和nums2[0]无法作为最小的k个pair了，因为已经有k个pair比他小了。
按图所示，这一步把（1，9）加入队列。为什么选nums1的下一个下标：排除掉nums1下标k-1之后的元素后，剩余的可能的pair中最小的就是（1，9）
第三步，得到第二小pair（也就是目前最小的pair），
为什么目前最小的一定在队列里：因为之前一步加入的候选者就是剩余可能性中最小的pair了。
这一步弹出来的是（7，2），下一个入队列的是（7，9）。理解：为什么不加入（1，10）呢？ 就是因为弹出的并不是（1，9），也就是说（1，9）并不是第二小，顶多是第三小，也就是说（1，10）不可能是第三小的，因此无需入队列。 而（7，9）是稍大于（7，2）的元素且候选者中最小的，可能作为第三小，因此进行队列。
第四步，依次类推。
总结，规律就是每次弹出的nums2的下标加1，nums1下标不变。
时间复杂度O(k * logk)。编码难点在于nums1中一开始元素不足k个。不足k个没关系，整体逻辑上还是正确的，只是难理解点。
方法二：m路归并，或者n路归并（m，n里面小的那个）：
画一个二维矩阵就明白了：1，7，11，16作为横坐标，2，9，10，15作为纵坐标，那么首先把第一列的和算出来，然后从中选择最小的，
取出，然后放入纵坐标加1的，横坐标不变的元素，因为我们知道，当前最小值一定是从每行最新头里面出，就是其中最小的那个。
实现的时候记录下每个pair的nums2元素所在的下标，然后每次下标加1取出下一个nums2元素，加上nums1下标不变的值。
时间复杂度O(k * logmin{m, n})。k如果比m，n小，那么选方法一，k的范围其实是1到mn，所以比m，n大是很正常的，因此方法二简单可行（推荐）。 还要注意k可能比m/n大,此时题目要求返回所有pair。
此题规定了k很小，而m，n很大，因此方法一最佳。
PS.
-
优先级队列的套路就是把k个元素放入队列，这样下次元素就是相当于和k个元素同时比较，理解： 求一次考试的全班前k名，如果一个人知道已经有k个人分数比自己高了，那么自己绝不会是前k名。
-
此题类似于super ugly number题，也就是每个新生成的最值会对下一个候选者产生影响，而候选者往往是从几个数里面挑出来。通常解法就是优先级队列，一开始放入所有候选队列的队列头，然后每次取出来一个最值，然后更新候选队列的头。
659. Split Array into Consecutive Subsequences
题意：给出升序整数序列，现在要把其中的连续（相差1）序列（不需要相邻）01的方式拿出来，如果拆出来的序列都是长度大于等于3，那么返回true，否则返回false。
解：有点打牌找顺子的感觉，本质是贪心。思路是： 从小到大顺序的看，把第一个元素看作是起点，先连两个再说，如果连不了，那么说明找不到，对于后面的元素，如果它还没有被连， 那么它只有两种选择是合法的（最终落入到某个顺子里）：一种是作为结尾加入之前搞出来的某个顺子，第二种是自立门户，也就是当起点情况看，直接后面连两个元素。 总结起来，就是假设每个元素最终都落入某个顺子，然后开始对每个元素看，两种情况，要么作为起点，要么接到前面的某个顺子里。
再来看编码，我们需要记录每个顺子的结尾数字（可能不止一个），具体来说，就是需要支持可删除（更新）的，可以快速查询是否元素存在的数据结构，也就是hash表 记录num -> 以num为结尾的顺子数量。
具体编码：先把每种数字对应的数量存到freq表（哈希表），然后遍历的时候使用tail表（哈希表）来记录以i为结尾的序列个数，注意tail表中记录的序列要保证比3长。
如何做到比3长呢？每次处理数字i的时候，看tail表中是否存在存在i - 1结尾的序列，如果不存在，那么看freq表中是否还有多余的i+1和i+2，如果都有多余，那么将i+1和i+2取出来，tail表中以i+2结尾的序列数加1
如果存在i - 1结尾的序列，那么将i - 1结尾的序列个数减1，然后以i结尾序列个数加1，
如果都不行，那么就返回false表示此数无法凑成3个以上的序列。
理解：每个数尽可能被消耗掉，要么作为之前存在序列（大于3的）的结尾，或者作为新起点。 方法二将时间复杂度降到O(n)。
PS. 此题解法其实是贪心，而不是某种”科学”解法。贪心的合理性：
为什么不考虑这个数作为中间数？例如，单独结合i-1和i+1？
因为之前的i - 1已经概括这种情况：i-1如果可以归并到i-2，那么i也可以归并到i-1；如果i-1不可以归并到i-2，那么i-1直接往后看两个元素也把当前情况涵盖了。
402. Remove K Digits
题意：给出数字串，然后给出删除的次数限制k，求删除后得到的最小的数字串大小。数字的次序不发生变化。
解： 此题一开始想到的是dfs，dfs需要对每个数字考虑是否删除，然后继续向下一层搜索，花费的时间是n个数字中选k个的组合数，k大约为3的时候，时间复杂度几乎为O(n^3)。这样时间复杂度太高。
一般来说，不简单的题目往往是经典算法能解的，而是需要找规律。
删除k个数字，其实是选出n-k个数字。 先看实例，如果是12345678，k=4，那么答案就是1234。规律是选前面小的部分，后面5678数字大，不选。
如果是87654321，k=4，那么答案是4321。规律是选后面小的部分，前面的8765部分大，不选。
如果是123451，k=1，那么答案是12341， k=2，那么答案是1231， k=3…。规律是保留顺序，但是删除掉中间的大数字。
如果是3261，k=2，那么答案是25，规律是保留顺序，但是删除掉前面，中间的大数字。
总结起来，规律是什么呢？关键一是保留顺序，关键二是如果后面的数比前面数小，那么前面的数要删除掉。 也就是说，要尽量维持一种升序，如果遇到违反升序的数字，那么替换掉之前的最近的数字，替换的策略是尽量替换，也就是能替换几个是几个， 在次数够的情况下和能替换的情况下。
规律本质就是：越靠左边的高位值要尽可能小。
使用单调栈来解题：从左到右选择递增的值加入最新的结尾，如果出现递减的情况，那么将在考虑删除次数限制的情况下，将单调栈里面能更新的数全部删除，之后加入最新值。
得出结果后，还要注意边界情况，一个是结果是空的，或者结果是0开头的串,以及结果串大于所要求的res的长度。空的时候说明全部可以删除，所以答案是’0’，结果是0开头的串，要把之前的0删除掉。串大于结果长度时候，先要resize，只保留升序的前面部分。
330. Patching Array
题意: 给出有序的数字数组nums，然后给出一个n代表1到n的区间，nums中元素01组合的和可能介于1到n，现在要保证组合和能覆盖1到n，求nums中缺失的最小数字为几个。
解：此题使用贪心法。设置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”。现给出压缩串，还原。其中压缩的原理是如果字母本身数量是1，那么维持原样，这样才能保证压缩是减小的， 注意给出的s都是合法的，不会出现非法的例如”3a[b]”
解：扫描，知道遇到]的时候，要结合之前的3进行还原，因此此题使用栈。
为了快速区分栈顶是字母还是数组，干脆分为数字栈和字母两个栈，
每次遇到“[”的时候，意味着子函数开始，使用res变量记录新函数的结果，但是res此时前记录的是父函数的结果，所以这时候需要”保护现场”：也就是把res存起来（存到栈里）， 然后将res清零。
每次遇到“]”的时候，意味着当前函数要结束了，此时res记录着此层的结果，但是不要忘了，此次函数计算的结果返回给上一层，具体做法就是：先把res乘以k倍， 然后把之前保存的上一层的临时结果还原回来，也就是出栈，然后之前的值加上res乘以k得到当前函数的最新结果。 最终的结果就是res，因为解的就是一个大函数。
理解：此题属于模拟函数递归返回过程，需要记住这种常用套路：
res记录当前层结果，进入下层前，先保存上一层结果，然后res清零；返回上层的时候，把之前保存的值拿出来，然后加上当前计算的结果。
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] 解：先简化这个问题，有助于思考。先来看，如果规定只能从两个数组里面分别选一个数字，那么我们肯定是选两个数组里面最大的数字，然后 进行结合，把两者中较大的数放前面。进一步，如果只能从两个数组里面分别选两个数字，那也是分别选出最大的二位数（这和402题是相同问题）， 然后进行合并，假设之前选出的是56和73，那么答案是7563，这个合并原理就是二路归并，使用双指针就可以解决。
也就是可以分解为两个问题：
第一个问题：从一个nums数组中保持顺序取出i个数字能组成的最大数为多少。
解法是：例如[9, 1, 2, 5, 8, 3]，那么i = 2，那么98最大，如果i = 3，那么983最大。
使用402单调栈解法，扫描一遍数组，保持一个需要丢弃的总数，当前扫描数如果比栈顶大，那么看丢弃数是不是> 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中含有负数。
解：所有子数组为n^2个，然后要满足两个条件，也就是进行两轮筛选，花费O(N^2)时间，也就是暴力求解。
优化的思路就是，不先求出全部n^2个子数组，而是利用计算子数组的某种性质，来提前减去无用的计算。
先考虑递增的滑动窗口优化，由于其中包含负数，所以不行。
正确的思路是preSum + 可删除的滑动窗口。使用带时效的单调栈，也就是Deque，之前计算window里面的max的题目中也使用了deque。
对preSum数组求子数组来说，数学上就是对于每一个元素，它都可以结合比自己下标小的所有元素，因此解空间N^2，但是可以优化每个元素结合之前元素的数量：
也就是说，利用之前元素的一些性质，也许需要依赖的只是若干，具体来说：
维持一个deque，deque中的元素对于当前扫描元素来说，都是比自己下标小的且考虑过的元素，作用是作为搭档，为最终最优解提供候选解。
该deque特点：Deque中元素从左到右（左侧为front，右侧为back）一定下标递增，因为每次从deque的右侧压入preSum数组元素；
Deque中元素从左到右大小递增，这个性质需要维持。nums[left] < nums[right]。
先看deque的最左端元素（设为left）结合当前元素cur对最终最优解的影响：如果cur - left大于等于K了，那么可想而知，下一个扫描元素，即使减去这个y满足大于等于k条件， 但得出的下标跨度只会更大，因此不可能作为候选者，也就是说，left不会对于之后的扫描过程做出任何的贡献了，因此可以从front弹出。 但是注意弹出前，cur - left要作为候选值之一记录下来，因为left后面要丢掉了。
经过这个步骤后，left满足cur - left < K。
再看deque的最右端元素（设为right）结合当前元素cur对最终最优解的影响：
由于之前得到cur - left < K，且left < right，所以cur - right < K，没有候选值，此时我们看
是否cur - right < 0，如果是，那么对于right来说，右侧已经出现了更小元素了，自己对之后扫描元素没有任何更大下标跨度贡献了，所以right从back弹出，直到cur - right >= 0。
注意：当前元素每次都是必须无条件入deque的，以便之后的扫描元素参考。
因为每个元素只会入deque一次和可能出一次，每次进出的时间消耗都是O(1)，所有元素扫描处理一次就能得知答案，所以总时间复杂度是O(N)。
总结：1. 此题模型是寻找一个数组里面两个元素相减大于等于K，且两个元素之间距离最短的那个。
K大于0或者小于0，其实是不重要的。
- 无论如何，子数组问题都是一定要使用presum技巧来快速计算子数组大小的，计算presum使用n时间，presum数组的第一个元素默认为(0, 0)，然后每个元素num[i]在之前处理的presum里面找出num[i] - num[j] >= K（j < i）。
带时效的单调栈这种技巧可以解决的问题的特点是：求最值，最值被两个维度的信息所影响，且其中一个维度和下标有关，这样，通过单调栈保持下标递增的情况下，从栈的两端进行考虑，例如从左到右，把将来不会对最优值做贡献的元素去掉，然后从右向左做同样的考虑。
857. Minimum Cost to Hire K Workers
题意：要从N个workers选出K个组成一个组，求总工资最小的组。其中工资w要和打分q成正比，每个worker的工资要大于每个worker的期望。
解：先考虑如果已经选出k个人，如何计算总工资: 首先，根据数学知识，我们知道至少有一个人发的工资等于他的期望工资。反证：如果每个人发的工资都比自己的期望工资高，那一定存在水分。 然后，再跟据具体例子分析，
假设有四个人，期望工资分别为100，100，100，100；分数分别为1，2，3，4。 如果按第四个人为基准，发100，那么按照比例，之前的人是发不到100的，所以不符合要求。 如果按第一个人为基准，发100，那后面的按比例发200，300，400，符合要求， 如果，按照中间两个人发100，也不符合要求。 这种情况下，是按照最大w/q最大的那个人的w为基准。
再来分析另一个例子：100，200，300，400；分数分别为1，2，3，4。 这种情况下，显然按照谁做基准都可以。因为w/q都相同。 那么，再来看100，200，360，444；分数分别为1，2，3，4。 这种情况下，第一个人发100的时候，第二个人按照比例发200，是不到201的； 按第四个人发444，第三个人发333，也是不到360的。按第三个人发360就可以，第一个人发到了120，第二个人240。 第三个人和第四个人的区别是什么？那就是第三个人的w/q较大。
所以，根据数学知识的分析，知道，一定会选择对基于最大w/q的人发，发的时候，对每个人i发max{w / q} * qi。 总和就是max{w / q} * Q。Q为q的总和。 结论：要减少总工资，那么，首先q的总和Q要尽量小，然后max{w / q}要尽量小。
那么怎么从N个里面选K个呢？ 首先暴力解决的话就是从n个里面强制选K个，然后计算比较，这样复杂度太高。
可以优化，原因是可以避免掉这种完全随机的、整个空间的搜索，而是其中蕴含这一些规律，使得解空间其实没有想象的那么大。
仔细思考其中规律，K组里面的那个w/q的基准一定出自于N个w/q里面，这意味着什么呢？K组里的 w / q 其实已经比 k - 1个wi/q大了！！！这意味着看起来是从N个里面选w/q，
但是，应该只是其中的前N-k大的几个人才有足够的比他小的人数达到K！！！
也就是说，我们把基于前N-k个人为基准的总工资都算一遍，在里面选出最大的就是答案了。
把所有的wi/qi按照从小到大排列起来，那么只有wk+1，wk+2，…wN的人才有足够的比他小的人数。 其中，对于wk+1为基准来说，就是只有一种情况！对于wk+2为基准来说，就是在前面的K个人里面，选择一个踢掉，把自己加入进去（PS. 我是怎么思考N选k的？？是先搞一个随机的k组，然后把里面的 一个拿出来和未选择的进行交换得到新组）
再来考虑其中的踢掉的情况，怎么踢掉呢？那就是，前面分析过的，要保证总和Q尽量小，也就是说，在前面的K个人里面，把Q最大的踢掉。
对于k+2的人也是一样，把之前k + 1里面最大的2个踢掉。
答案呼之欲出，那就是先把wi/qi从小到大排序，然后先把前k-1个元素放入优先级队列，计算队列总和；
然后，依次考虑k，k+1，…N。
第k个元素，直接计算结果， 但是计算完之后，需要把自己放入优先级队列，然后把里面最大的q弹出来，更新队列总和。 这样优先级队列继续维持着k-1大小；
第k+1个元素，不要担心之前弹出来的那个元素，因为它必属于自己之前元素中最大的2个q元素之一； 对于自己来说，同样进行计算，然后把自己加入队列，弹出最大q，更新队列总和；
依次类推，在过程中记录下来拿次计算出来的值是最大的。
PS. 组合的优化解一定是发现了其中的规律； 对于这种两维度的问题，常见的解题思路就是先对某个维度进行排序来达到”降维”效果。
855. ExamRoom
题意：0到N－1表示连续座位的下标，现在人有坐和离开两种操作，坐的时候要满足离身边的人最远（如果有多个选择，那么选座位号码小的），离开操作题目保证一定可以是有效的位置。要求设计坐和离开两种操作。
解：此题是一种动态生成区间的题目，为了保证每次找到间隔最大的区间，可以使用优先级队列。
我们知道，坐操作的时候，选了点之后，会以自己为分割点分割座位。
把区间［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，解决方法是距离除以2向下取整作为选这个区间能获得的距离。 还有就是，区间［0，2］和区间［4，7］，包含端点的情况下，［4，7］的优先级更高。
如何构建优先级小结：如果包含端点，那么就是优先级最高，这个区间排最前面；否则看区间长度/2，大的排前面，如果相等，那么选择下标小的区间。
PS.优先级队列的operator里面大于小于的理解：只有为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
题意：行星碰撞。给出整数数组，元素代表行星的大小和移动方向（正表示向右、负表示向左），行星移动速度相同。
如果大行星撞到小行星，那么小行星爆炸（消失），大行星保留，如果质量一样大，那么都消失。 现在求数组的最终状态。理解：可以理解数组里面只是放了这些行星，行星移动的时候是没有边界的，例如全是正数，那他们之间是不存在碰撞的。
具体来说：Input: asteroids = [5,10,-5] Output: [5,10]
Input: asteroids = [10,2,-5] Output: [10]
解：其实就是求最后剩下的元素。对每个元素，如果是正数，如果要活下来，那么他的右侧不能有绝对值比他大的负数， 或者有，不过被自己之后（负数之前）的更大元素干掉了，而活下来与左侧无关。如果是负数，取决于左侧有没有比他绝对值大的正数且这个正数之前没有被干掉。
所以，此题有点单调栈的性质。
从左向右看，如果第一个数是负数，那么他会保留，扫描下一个；
如果是正数，那么向后看，进行一个”单调栈”处理，如果是正数，那么入栈保留，如果是负数，那么看栈内元素， 如果比它的绝对值小，直接删除，如果栈为空（或栈顶为负数），那么说明负数存活下来，或者遇到绝对值比自己大的，那么被干掉，在继续向后看，如果是正数，直接加入栈，负数则重复同样过程。
编程技巧：使用vector模拟栈，在碰撞时候，如果栈上元素被摧毁，当前元素保留，可以使用i–的技巧重新考虑当前数， 或者启动一个单独的循环。
1249. Minimum Remove to Make Valid Parentheses
题意：字符串S，求删除最少的左右括号得到的任意一种合法字符串。例子： Input: s = “a)b(c)d” Output: “ab(c)d”
解：此题和301题相似，但是不需要求出所有Valid Parentheses变体。使用301的BFS解法是会超时的。因为此题要深刻挖掘使用括号匹配的特殊规律。
这个规律就是：要删除的左右括号，其实就是在括号匹配过程中剩余的，具体来说：
左括号的剩余情况就是： 这个左括号右侧的右括号全部已经被匹配了； 右括号的剩余情况就是： 右括号的左侧的左括号全部已经被匹配了。
可以知道：左括号是否剩余，必须等到整个匹配过程结束才知道，而右括号是否剩余，在匹配过程中就知道。
因此，方法就是括号匹配，从左到右依次扫描，使用栈记录尚未被匹配的左括号的下标，如果发现右括号，那么将最近的左括号的下标（匹配上了），也就是栈顶进行删除；
如果栈为空，说明左侧的左括号全部已经被匹配了，此时将要删除的右括号位置记录下来。
最终栈中剩余的就是剩余的左括号下标位置。
最终删除所有剩余的左右括号，得出最终结果，
具体编码，维持栈结构，里面放入待匹配的左括号下标，最终剩余的是需要删除的左括号下标， 使用数组记录没有被匹配的右括号下标，最终删除掉。 方便编码，加一个标记数组，标记原字符串的那个位置需要删除，最终扫描一遍，用stringbuilder收集到所要的剩余串。
