春季四个月刷题

5.22 做题

11. Container With Most Water. 这个题目使用双指针相向而行，每一次的一个双指针组合，都算出两个挡板能够盛装的水，然后和当前已知的最大值进行更新；然后对于这两个指针，找到当前指针对应高度较小的那个，移动对应的指针

42. Trapping Rain Water. 这个题目使用的方法是左右两次遍历、再使用遍历后的每一个对应位置上的两种结果进行比较获取最后的结果；首先从左往右进行DP遍历，对于每一个位置的元素，都把当前的元素和前一个位置对应的DP数组元素比较，如果当前的元素更大，就说明到了这里可以兜住更多的水，DP数组的当前位置取这个元素，否则就继承前一个位置的DP数组元素；然后从右往左进行DP遍历，和上面同样的方法；最后完整遍历一下数组，对于每一个位置，找到两个DP数组对应位置的元素的较小的那一个，减去相当于底部的原本数组该位置上的元素，依次相加，就相当于全部的盛水量

334. Increasing Triplet Subsequence. 这个题目本质上是寻找一个最长递增子序列的问题，因为要求找到一个递增的3元组；那么一个基本的最长递增子序列，方法就是遍历给定数组，对于每一个遍历到的元素，都在已经构建好的递增序列中进行二分查找；如果该元素比全部构建好的序列元素整体要大，就说明可以扩展一个元素，否则就替换子序列中的某一个元素；而这个题目，可以简单直接使用一般的方法，并且当已经构建好的递增序列长度已经达到3的时候就说明已经找到了；而优化的方案就是，由于这里的DP数组最多只包含2个元素，到了第3个元素的时候就可以直接返回了，所以为了节省空间，只维护两个变量即可，一个是小的那个、一个是大的那个；遍历给定数组，如果当前元素比small小就更新small、比big小就更新big，而发现了比这两个都大的元素就意味着找到了这个三元组

128. Longest Consecutive Sequence. 这个题目最基本的办法是使用HashSet，首先建立一个Set并讲所有的数组元素都放进去；然后遍历给定数组的所有元素，对于每一个数组元素num，都看看num - 1是否已经存在于Set当中，如果存在就表示该元素已经被讨论过了，如果不存在的话就从当前元素开始不断加1并去Set当中进行验证，直到不存在于Set中，而这时持续累加的次数，就是以这个num元素为初始元素的连续递增序列的长度，并和全局最大进行比较；但是这个解法的问题在于，比如对于数组[1, 2, 3, 4, 5, 6, 7, 8]来说，其实本身就已经构成了一个连续增长的序列，并且所有的情况已经在第一个元素1的时候讨论完毕了，但是当遍历到2的时候，仍然要以2为起点连续增长并重复去Set当中进行验证，这就是不必要的操作；优化的方法是使用Map，对于一个元素num来说，如果这个元素num不存在于Map中，就说明当前不可能已经讨论过一个已经覆盖当前这个num元素的连续递增序列，那么首先检查num - 1和num + 1是否存在于Map中，如果存在的话就获取到对应的数值left和right；这里的这两个数值，分别代表着当前已经找到的，以num - 1为上界的连续递增序列的长度，和以num + 1为下届的连续递增序列的长度，而num的存在就意味着，这两个连续递增序列可以相互链接起来了，而新的连续递增序列的长度就应该是这两个数值之和 + 1，对于这个数值再去进行全局最大的比较和更新；接下来要做的就是，对于这个心的连续递增序列，需要对其上下边界进行更新，就是num + right和num - left，这是因为可能在接下来的遍历当中遇到另一个num使得可以吧这个连续序列和其他进行进一步连接；而对于这两个值更新的value则是left + right + 1

164. Maximum Gap. 这个题目的思路是使用bucket sort；首先对于给定长度为len的数组，找出其最大的元素和最小的元素，然后基于最大最小值算出一个gap，也就是用max - min再除以len - 1，gap就代表给定数组的平均间隔长度，len个元素就有len - 1个间隔，数组元素都会落在这些间隔当中，这就相当于是bucket了，每一个元素num都是根据num - min再除以gap，就可以算出它们落在哪一个bucket当中；现在希望获取到每一个bucket当中的最大元素和最小元素，因此就应该对于每一个元素num去计算它们应该落在哪一个bucket当中，全部分配好之后对于每一个bucket都找到里面的最大元素和最小元素；最后就是去找到，对于每一组相邻前后两个bucket，其前一个bucket的最大元素和后一个bucket的最小元素的差值，希望找到它们差值的最大值，就是maxGap；这是因为这些bucket间隔本身都是有序的，因此前一个bucket的元素都一定要比后一个bucket元素整体要小，而前一个bucket元素的最大值，就一定和后一个bucket元素的最小值，在排好序之后就一定是紧挨着的；而对于同一个bucket当中的元素，因为它们本身就处在同一个bucket里面，其间隔一定要比平均间隔gap小，这就肯定不会是答案，所以答案只能从相邻两个bucket之间的最大最小值进行寻找

5.23 做题

287. Find the Duplicate Number. 这个题目要找到一个数组当中的duplicate元素，并且已知该数组有n + 1个元素但有n个不同的元素，并且已知元素的范围是从1到n的；对于一般要找duplicate的话，最简单的方法是使用HashSet，但是这里给定了这些条件，就可以用swap的方法，因为只有一个元素是重复的，那么就只需要把每一个元素放到它应该出现的index上面，比如1应该出现0位置、5应该出现4位置、9应该出现8位置，具体来说就是，对于每一个元素，都去检查这个元素应该出现的位置上是不是已经存在这个元素了，如果没有的话就swap，如果已经出现的话就坚持这个元素的位置是不是它应该出现在的位置，如果是就继续，不是就说明找到重复了；但这个题目还要求，不能改变array，也就是说不能进行swap，因此另一种方法就是快慢双指针；这里的快慢双指针不是物理上的两步和一步，而是说slow每次都等于nums[slow]，而fast每次都等于nums[nums[fast]]，直到fast和slow是相同的，就说明出现了它们出现在了因为duplicate而存在的“circle”当中，接下来要做的就是重置一个指针在最开始，然后慢指针和重置指针每次走一步直到相遇，此时的慢指针就是duplicate元素；这个题目和在LinkedList当中找环的起点的问题一模一样https://leetcode.com/problems/fi ... ood-solution-with-O(n)-time-and-O(1)-space-without-modifying-the-array.-With-clear-explanation.

135. Candy. 这个题目本质上是一个DP题目，因为每一个位置总是应该从旁边元素的情况推导出来；题目给定一个评分数组，要求对于每一个位置，如果如果评分比两边要高，那么就至少应该比两边得到的candy要多；比如这个数组：1 2 4 3 6 5 0来说，4比它周围的2和3要大，因此就应该有更多的candy，而2比1大比4小，就应该比1有更多的candy、比4有更少的candy，而3位于4和6之间，就应该比这两个位置的candy都要少；首先从左往右遍历，对于每一个元素来说，如果它右边元素值要比它大，那么它右边元素就应该比它多1个candy；对于上述数组来说，就应该是1 2 3 1 2 1 1这样；接下来从右往左遍历，对于每一个元素来说，如果它左边元素值要比它大，那么它左边元素就应该比它多1个candy，并且这个情况是要建立在已经建立好的从左往右遍历完成的数组基础之上的，因此就会出现这样的一个问题：从左往右遍历时，可能遇到3 17 5 4 3 2这种数组，那么3是1，17就可以是2了；但是当从右往左遍历时，从2开始到3到4到5，到了17位置的时候，5这个元素的值要比17小，但是此时5这个位置已经有4个candy了，却又比17大；对于这种情况，在从右往左遍历的时候，只需要额外检查一下，当左边元素值比当前元素大时，如果左边元素的candy数量并不是比当前元素的candy数量多1个，那么就对左边元素的candy数量进行更新即可；也就是说在从右往左遍历时，在之前的基础上进行一次额外的检查和更新，这样就可以保证出现上述特殊情况时，一个真正的peak可以满足于两边的candy数量

330. Patching Array. 这个题目应该使用Greedy的思路；对于一个已经排好顺序额度数组来说，从左到右进行遍历组成一个从0开始到i的subarray，而对于这个subarray的元素之和sum，如果希望从1开始到sum之间的所有数字都可以被这个subarray当中的元素所组成的话，就一定要满足对于每一个i来说，这个位置上的元素一定要比这个位置之前的整体subarray元素之和sum要小；比如1、2、3、9这四个元素，对于前面三个值1、2、3来说，它们的和等于6，而第四个元素是9，那么就说明这个subarray无论如何也无法组成7、8这两个元素，那么解决的方法就是给这个subarray填入7这个元素，从而使得1、2、3、7的和为13，当然就可以组成7、8，并且13这个sum大于9，因此就可以组成从1开始到22的所有元素；因此方法就是，从左到右进行遍历，对于每一个位置都去算从0开始到这个位置的subarray的sum，并且使用这个sum去和下一个元素比较；如果sum比下一个元素大，那么就把下一个元素加进来组成更长一位的subarray和更大的sum；如果sum比下一个元素小，就说明从sum开始到下一个元素数值之间有元素不能组成了，因此就要补充sum + 1，也就是上面例子的7；重复这个补充的过程，每次都要补充上当前sum的sum + 1，直到能够越过下一个元素为止；持续以上的这个过程，直到sum大于等于n，或者如果到了最右端依然不到n，那就继续补充即可；具体解释https://leetcode.com/problems/pa ... my-thinking-process

38. Count and Say. 首先使用recursion的方法，获取n - 1的String，然后使用快慢指针进行遍历，从0开始快指针往前走直到和慢指针指向的字符不一样，然后此时快慢指针的差值就是该字符重复出现的次数，将次数和字符append到结果中去，再重复这一过程，直到快指针走完

316. Remove Duplicate Letters. 这个题目的意思就是，对于给定的一个String，首先尽量往后找到一个字符，使得这个字符是当前String按照字母表顺序出现的最小的字符的最后出现的那一个位置；然后从这个为止开始，对于后面的剩余字符串，进行recursion操作，当然对于recursion的这部分，还需要把这个字符给去掉；总之是greedy的recursion，不是特别懂，还有用stack的

5.24 做题

168. Excel Sheet Column Title. 这个题目就是将10进制的给定整数，转化为一个26进制的字母组合；对于给定整数，就需要对其进行循环，每一次循环内部都首先对26取余，得到的余数就应该被添加到结果当中，同时再除以26得到的商就是下一次循环中的整数；这里首先注意，如果使用数字减去'A'字符的方式，那么就应该是0到25，因为A减去A等于0，Z减去A等于25，所以每一次循环的整数都应该先减去1；另一方面，对于n对26取余得到的数字，其实就应该是对应了一个从A到Z的字母，用这个数字减去A再转化为char就是当前的字母了，这个字母就可以添加到结果当中去了

171. Excel Sheet Column Number. 这个题目是前一个题目的逆转；对于给定的一个字母序列，从左到右进行遍历，对于每次遍历到的字母，都首先转化成为数字，方法就是用这个字母减去字母'A'然后加1，比如A减A等于0，加1的等于1，Z减A等于25，加1等于26；对于转化完毕的数字，就加到结果当中去，当然首先结果要乘26再加；这就是一个26进制转化为10进制的方式，每当遍历到一个字符以后，原有结果乘上进制数，然后加上该字符所代表的再新的进制下的数字即可

13. Roman to Integer. 这个题目要把一个Integer转化成罗马数字表示，也就是IVXLCDM这种字母去表示数字；这些字母表示的分别是1、5、10、50、100、500、1000，对于所有1开头的字母来说，它们除了可以表示“添加”1开头的数字，还可以表示“删减”1开头的数字，而所有5开头的字母就只表示“添加”5开头的数字；比如对于I来说，如果它出现在V或X或其他字母的右边那就表示“添加”，但如果出现在它们的左边那就表示“删减”，即：VII表示5加上2等于7，但IV或者IX却表示5减1等于4、和10减1等于9，同理XL表示40、而LXX表示70；根据这种规则就可以看出，当从右往左进行遍历罗马字符串时，每当遇到V、L、D时，就直接往结果当中添加5、50、500就可以了，而每当遇到I、X、C时，就需要判断它们究竟是出现在其他字母的左边还是右边；这里对于1开头的字母来说，可以去对它们向左向右查找，当然同样也可以根据已经构建的结果进行判断：如果当前构建的结果小于5，那么毫无疑问现在已经遍历到的罗马字符串只能是I或者II的，因此如果再遇到了一个I，那么只能往结果当中加1；而如果当前构建的结果大于等于5，比如是V或者X，那么如果这时再遇到了一个I构成了IV和IX，那么自然就是往结果当中进行删减变成了4和9；对于X、C字母也一样，当结果已经大于等于50、500的时候，遇到了X、C就应该从结果中删减10和100，否则就添加10和100

12. Integer to Roman. 这个题目首先需要构建起来两个数组，一个数组用来存放所有罗马字符所代表的数字，一个数字用来存放所有对应的罗马字符，即{1000,900,500,400,100,90,50,40,10,9,5,4,1}和{"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"}这两个，注意这里不仅包含了单个的I、V、X、L、C、D、M，还包含了CM、CD、XC、XL、IX、IV这种字母；从上一个题目可以直到，对于以1开头的字母来说，如果它们放在了其它字符的左边就代表着要减去相应的数值，这里把这种情况罗列出来，单纯就是为了方便讨论而已，也就是说当罗列出这些数字以后，接下来构建罗马数字的时候就只需要考虑“添加”的情况而不需要考虑“删减”了；从前往后开始遍历这两个数组，也就是从大到小的顺序，对于每一个数字来说，都用给定的Integer去减，持续减，每减一次向结果当中添加该数字对应的字母，直到当前Integer小于当前的数字，然后再进行下一个数字的讨论

273. Integer to English Words. 首先对于一个给定的数字，应该对其不断地对1000进行取余，每一次取余后获取到的3位数进行英文单词的组合，然后让该数字除以1000，再重复这样的过程；每一次通过对1000取余而构建好的3位数英文组合，再下一次循环中，都应该作为后面的词组，新组成的3位数应该放在已经构建好的词组的前面，中间加上对应的英文单词Thousand、Million、Billion等；对于每一次构建3位数英文单词，首先要看当前3位数是多少，如果是小于20的话直接替换成单词，如果是大于20但小于100的话，就先除以10得到一个个位数再替换成对应十位的单词，然后后面再加上对10取余以后的数字的recursion，如果是大于100但小于1000但话，就先除以100得到一个小于20的数字并替换成单词，后面加上Hundred后再加上对100取余后的数字的recursion

5.24 做题

326. Power of Three. 这个题目可以用recursion的方法，也可以用iteration的方法；本质上就是用给定的整数，除以3和对3取余，这和进制转换、整数转字母的套路都是一样的：对3取余就代表着，当前这个数字除以3以后还剩下了什么，余数就相当于是一个被减去的部分；除以3就代表着，当前这个数字一共包括有多少个3，商就相当于是当前整数剩下的部分；比如一个整数19683，如果希望判断它是不是3的power，首先应该检查它除以3以后能不能除得尽，也就是说应该用19683 % 3看看是否等于0，如果是等于0的话，就用19683 / 3 = 6561，再重复这样的一个过程；直到最后检查一下，这个整数不断除3会不会变成1，如果是1的话那就说明这个整数原本就是3的power；而对于另一个整数36，先检查36 % 3等于0可以除的尽，那么就更新这个整数为36 / 3等于12，然后又发现12 % 3等于0也可以除的尽，那么就更新这个整数为12 / 3等于4，然后发现4%3不等于0除不尽了，最后就判断一下剩下的数字是多少，发现是4而不是1，所以36就不是3的power；基于这样的一个思路，就可以使用recursion或者iteration的方法了：recursion的方法就是，对于当前的整数，首先检查一下是不是1，如果是1的话就是3的power，而如果不是1但同时这个数字大于等于3并且可以被3整除、也就是这个数字对3取余等于0可以除的尽的话，那么就调用recursion、将传入的参数设置为当前数字除以3的结果，而除此之外的情况则都不是3的power；iteration的方法就是，对于当前的数字，只要它大于等于3并且可以被3整除、也就是这个数字对3取余等于0可以除的尽的话，那么就一直对这个数字除以3并且进行更新，直到这个数字不再能够除以3除的尽或小于3为止，检查当前数字是否为1即可

342. Power of Four. 这个题目当然可以使用前面的3的power的方法去做，但是由于这是4的power，可以采用二进制bit的方法进行判断；首先是2的power，2的power在2进制表示上，其特点总是只有最左边的一位是1，而后面全都是0，因此就可以使用num & (num - 1) == 0来判断，即1000000和0111111进行&操作看看是不是0，来判断num是否满足1000000的形式；那么4的power和2的power很像，不同点在于4的power里1后面的0总是偶数，比如100或者10000或者1000000，分别代表4、16、64，而比如1000或者100000就代表8、32就不是4的power；所以对于4的二进制表示，可以在2的power基础上，添加一个对1的位置的判断，由于4的power的1后面的0总是偶数，因此4的power的1总是出现在奇数的位置上，因此只要把这个二进制表示，和一个奇数位上全是1、偶数位上全是0的二进制表示数进行&操作，看看结果是否不为0就可以了；因为现在已经可以确定这个数是2的power了，也就是说这个数字的二进制只有一个1，那么接下来和这样一个奇数位上全是1、偶数位上全是0的二进制表示数进行&，如果这是4的power的话，它的1一定出现在奇数位上，那么结果一定不为0，否则如果1出现在了偶数位上，结果肯定是0了，因为没有任何两个位置上这两个数字都是1

372. Super Pow. 这个题目要掌握的公式就是ab % k = (a%k)(b%k)%k，转化为函数的形式就是f(a,1234567) = f(a, 1234560) * f(a, 7) % k = f(f(a, 123456),10) * f(a,7)%k，其中1234567就是最初始的b；代码可以在这里看到https://leetcode.com/problems/su ... on-using-fast-power

233. Number of Digit One. 这个题目的解释在这里https://leetcode.com/problems/nu ... -easy-to-understand；算的就是对于这个给定的整数，不断对其不同位数上进行累加然后看看有多少个1

5.25 做题

4. Median of Two Sorted Arrays. 这个题目应该明确的就是，对于两个sorted数组，它们各自都有着自己的中间值，而两者共同的中间值，要么比a中间值大且比b中间值小，要么比a中间值小且比b中间值大；因此思路就是每次recursion的之前，都去比较两个数组当前的中间值，如果aMid比bMid大，那么下一步recursion的范围，当然就应该是aStart到aMid，以及bMid到bEnd，接下来再在这个范围内把它们看作是新的数组进行recursion即可；具体来说，首先拿到两个数组，先要算出来它们的长度，由于它们长度之和可能为奇数也可能为偶数，所以就需要分别获取到这两个sorted数组中全部元素的第(len1 + len2 + 1) / 2个和第(len1 + len2 + 2) / 2个，再对这两个数进行求取平均值，这样的话就可以确保找到中位数了；在recursion当中，做完基本的base case检验，即检查当前所要查找的范围是否valid、当前a和b两个数组的start位置是否仍然在数组长度之内，并且检查当前的第k个元素是否为1，就可以进行recursion了；recursion的时候，根据上述思路，首先要确定的是，究竟是aMid对应的aValue更大还是bMid对应的bValue更大，即究竟是要比a中间值大且比b中间值小，还是比a中间值小且比b中间值大，这就要决定了接下来recursion的范围，然后进行recursion、根据aValue和bValue的大小，如果aValue更大，那么肯定整体的中间值是比aValue要小，所以a数组的范围应该是aStart开始、b数组的范围应该是bMid开始，反过来也是如此

321. Create Maximum Number. 这个题目的思路就是，对于给定的两个数组nums1和nums2，长度分别为n和m，要从这两个数组当中取出k个元素，组成一个更大的数组；那么也就是说，一共取k个元素，nums1取i个、nums2取k - i个，然后再去看看nums1应该取哪i个、nums2应该取哪k - i个，取完了以后变成了长度为i的新的nums1'、和长度为k - i的新的nums2'，最后将这两个新的nums1'和nums2'进行合并，成为最终的数组；那么对于i来说，也要对其进行循环，对所有nums1可以取到的i、nums2可以取到的k - i进行循环，每一次循环的i都可以最终造就一个最终数组，每次再取比较这些最终的数组看看哪一个最大就可以了；以上就是这个题目的思路，然后就可以逐步进行化简成小的问题：1. 在确定好i之后，直到nums1应该取i个、nums2应该取k - i个从而成为新的两个数组，那么这里的取法应该要保证新的两个数组各自都是在i和k - i的长度下最大的取法，因此这里的问题就变成了，如何从一个数组当中、取出i个元素、使其成为新的最大可能取到的数组；2. 在拿到新的nums1'和nums2'之后，如何进行合并才能成为最大的最终数组，也就是说现在两个数组的全部元素都会被加到最终结果数组当中，但是应该怎么组合才能使这样的结果数组最大；3. 如何判断和比较两个数组所代表的元素更大，这会在每一个i得到的数组和全局数组的比较更新当中使用到，也会在合并两个新的数组时，检查两个数组当前的哪一个元素更大的时候使用到；以上三个小问题就对应着代码中的maxArray方法、merge方法、greater方法

99. Recover Binary Search Tree. 这里给定了一个BST，BST的inorder打印肯定是sorted的，那么如果一个BST中间某两个节点被错误的调整了，那么BST的inorder打印就会出现问题，也就是打印后的序列肯定有两处、前面的元素大于后面的元素的情况；对于第一个前面的元素大于后面的元素的情况，肯定是因为本应该出现在序列后方的元素被调整到前面来了，那么出了问题的就应该是前面的、也就是较大的那个元素；对于第二个前面的元素大于后面的元素的情况，肯定是因为本应该出现在序列前方的元素被调整到后面来了，那么除了问题的就应该是后面的、也就是较小的那个元素；因此对这个给定的BST进行inorder的遍历，同时记录下每一个当前遍历节点的前一个prev节点；对于每一个节点来说，如果它比前面的prev的数值小，就要看看这是第几处情况，如果是第一处，那么除了问题的就是prev，记录下来，如果是第二处，那么除了问题的就是当前节点root，记录下来；然后把这两个节点的value调整一下就可以了；如何判断是第几处，就应该去检查当前保存结果的两个节点到底是不是空的，如果保存第一个节点是空，就说明是第一次遇到，否则就是第二次遇到

284. Peeking Iterator. 这个题目需要实现的是一个拥有peek功能的iterator；iterator的基本的两个功能分别是，hasNext和next，一个是判断是否有下一个，一个是获取下一个；而这里要添加的peek功能，是“看一下”下一个而并不是获取并拿走下一个，就和stack的poll和peek一样；那么思路就是，使用一个额外的变量去维护这下一个元素，那么peek方法就只需要返回这个元素即可，同时也不会真的获取并拿走下一个；而hasNext方法就只需要判断这个元素是否为null就可以了；那么对于next方法来说，真正要获取并拿走下一个，首先要返回的肯定是这个元素，另一方面由于需要真的拿走下一个，那么就应该调用题目中所提供的原始iterator的next方法：首先使用给定的iterator，使用hasNext检查是否有下一个，如果有的话就使用iterator的next方法，把获取到的下一个元素保存到题目中额外的变量当中，如果没有的话就把这个变量设置为null；这样就可以实现对这个额外变量的更新了

5.26 做题

146. LRU Cache. LRU的意思是least recently used，也就是说这个缓存有一个定额capacity，当缓存内数据量达到这个capacity以后，要从缓存中剔除的数据应该是那个被使用时间离当前最久远的数据；这里需要使用一个双向链表和一个Map，双向链表的节点则包括了真正要被存储到缓存中的key和value，而Map用来存储缓存中的key和双向链表的节点；Map的存在是为了可以根据key立刻找到双向链表中对应的节点，获取到value的同时还可以进行一些必要的LRU操作；为了实现LRU，不能仅仅在删除的过程中再去检查数据的使用时间情况，而是应该在每次使用数据时就进行一些操作：每次使用的数据，都是当前缓存中最新一个被使用的数据，那么从删除的角度上来说，这个数据就应该在当前的缓存中最后一个被删除；对于LRU的双向链表，如果规定尾部要删除、头部是最新的话，每当使用一个数据时，都应该把该数据所对应的节点转移到双向链表的头部；使用一个缓存的数据，可以是get操作，也可以是put操作；因此LRU本身内部应该包含一个双向链表节点类，链表节点除了自己的prev和next之外，还应该有key和value；LRU的成员变量应该有表示双向链表的head和tail，用来存储key和链表节点的Map，以及当前数据量total和最大承载量的capacity；初始化LRU时，就是初始化map、双向链表的head和tail互相指向、total设置为0、capacity赋值的过程；LRU的get操作，首先应该从map当中获取给定的key有没有对应的链表节点，如果有说明缓存中存在相应数据、否则直接返回-1，从map中获取链表节点后，就相当于这个节点所代表的数据被使用了，因此基于以上的分析，就应该把该节点转移到双向链表的头部，这个操作就是moveToHead操作，然后再返回该节点的value；LRU的put操作，首先应该从map当中检查是否已经存在这个key了，如果已经存在就应该更新该key代表的数据所对应的节点的value，因此就应该从map当中获取该数据、为该数据的value重新赋值，并且这个操作也相当于该数据被使用了，所以就应该把这个数据所对应的节点移到双向链表的头部，这同样是一个moveToHead操作；而如果这个要被put的数据的key并不存在于缓存当中，这时应该进行的操作就是一个简单的插入操作，即把数据分别插入到双向链表和Map当中，因此首先建立起一个等待put的key和value对应的链表节点，将该节点添加到双向链表头部，并且添加到map当中，这其中就包含了add操作；最后，由于是直接向缓存中插入一个新数据，就需要注意潜在的数据过载问题，即当前数据量total超过了最大承载量capacity，所以在插入完毕数据和节点后，首先应该更新total使其+1，然后比较total和capacity，如果已经过载那么就进行LRU、删除缓存中使用时间离当前最久远的数据，这就是removeLRU操作；对于以上过程中所涉及到的操作，本质上都是对双向链表的一些操作；首先是moveToHead操作，将当前使用的节点移到双向链表的头部，本身又包含了将该节点移除的remove操作、以及将该节点添加到双向链表头部的add操作；remove操作就是对于当前的节点，让它的next的prev等于它的prev，让它的prev的next等于它的next；add操作就是首先获取整个双向链表的head节点，让待插入节点的next等于head节点的next、让待插入节点的prev等于head节点、让head的next的prev等于当前节点、让head的next等于当前节点；removeLRU操作，从LRU中删除最久远使用的数据，首先应该做的是从双向链表中删除其最末端的节点、也就是popTail操作，然后从Map中删除掉这个末端节点的key对应的Node、同时更新total使其-1；而popTail操作，就应该是获取到双向链表的tail节点后，直接让tail节点的prev等于它prev的prev、并且让tail节点的prev的prev的next等于tail即可

355. Design Twitter. 这个题目要design一个Twitter，希望实现发推、关注、取消关注、获取NewsFeed这些功能；Twitter作为一个大的类，内部应该有一个Tweet子类；Tweet子类应该拥有的成员变量，是表示推文的tweetId以及表示发推时间的postTime；Twitter大类应该拥有的成员变量，是表示最大NewsFeed数量的MAXFEED、表示全局时间戳的timestamp、存储每一个用户的关注人集合的followees这个Map、存储每一个用户的发推列表的tweets这个Map；这里要注意的就是，Twitter大类的全局时间戳timestamp是属于整个系统的，而Tweet子类的发推时间postTime是属于每一条推文本身的，这两者的联系是，每一条新发送出来的tweet的发推时间postTime，都应该取当前的全局时间戳timestamp，而随后全局时间戳timestamp还应该加1，以提供下一条tweet的发推时间，通过这种方式，就可以确定所有tweet的发推先后，最新的tweet总是拥有数量更大的postTime，并且不同用户的发推总是可以通过postTime相互比较发推次序的；首先对于关注功能，给定一个关注者Id和被关注者Id，首先根据关注者Id去followeesMap当中检查是否已经存在当前用户，如果不存在就应该先在这个Map去插入关注者Id和一个空的Set，然后从Map中获取到被关注者的Set并往里添加被关注者Id；对于取消关注功能，首先根据关注者Id去followeesMap中检查，如果不存在该用户，或关注者Id和被关注者Id相同，就直接返回（逻辑上不允许），否则直接获取到当前用户的被关注者Set，并从中remove该被关注者的Id；对于发推功能，给定一个发推者Id和推文tweetId，首先去检查发推Map的tweets中是否有当前用户，如果没有说明该用户是新用户，应该在tweetsMap中进行插入新的用户Id和推文列表，同时条用关注方法，让发推者关注自己，然后从tweetsMap中获取到该用户的推文列表List，添加给定的推文至List的最前列，这是为了在获取NewsFeed时方便获取最新的推文；对于获取NewsFeed功能，是给定了一个用户，返回的应该是这个用户所关注的所有用户的一定数量的最新推文，那么就应该根据该用户去followeesMap中，获取它关注的所有用户，然后对于每一个被关注的用户，都去tweetsMap当中获取该用户的推文列表，接着就应该创建一个能够存放Tweet并且根据Tweet发送时间进行从新到旧排序的PriorityQueue，对于每一个被关注用户的每一条推文，都放进PriorityQueue中进行验证，而PriorityQueue也应该维持着预设NewsFeed数量的size；由于PQ是根据postTime排序、而postTime又是数值越大越表示最新发推，因此这里的PQ应该是最小堆、postTime数值较小的会在heap顶，每当有一个postTime数值更大、即新的tweet放入到PQ中，PQ当前顶部的postTime较小、较旧的tweet就应该被poll出来，所以通过这种方式，让每一个被关注用户的每一条推文都放到这个维持MAXFEED数量的最小堆中，遍历结束后PQ中就会拥有最新的若干条Tweets，这时把它们一个一个poll出来、并且postTime越大的越靠前，就组成了NewsFeed的结果了

303. Range Sum Query - Immutable. 这个题目就是要求一个数组的从i到j位置之间的所有元素和，这种问题当然要用prefix sum的思路来做，即对于给定数组，先创建一个prefix数组，从初始位置的数据一直进行累加，使得prefix sum的每一个元素，都表示给定数组从0位置到当前位置的所有元素之和；这个题目是一个Design题目，需要给一个构造函数和一个sumQuery方法，构造函数的内部就应该是根据给定数组构建prefix，而sumQuery就是根据给出的i和j，去使用prefix数组，prefix[j] - prefix[i - 1]，得到最终结果返回

304. Range Sum Query 2D - Immutable. 这个题目同样要做prefix，只不过prefix本身也是2维的，构建prefix的时候，应该由它的左边prefix值和上边prefix值，减去它左上方prefix值，再加上当前位置的matrix值；给出sum的时候，应该由给定范围的右下角prefix值，减去左下角prefix值和右上角prefix值，再加上左上角prefix值

5.27 做题

68. Text Justification. 这个题目需要进行非常详尽的分解，首先对于给定的String数组和max，应该确定加到结果中的每一行的left和right、即最左和最右单词在String数组中的index，然后对这个范围内的单词元素进行justify、即把这些单词中的空格留出来，最后把justify完毕的每一行加到最终结果里；对于根据max循环找每一行的left和right，left自然是从0和right + 1开始，而right则是从left开始每次往后查找一位单词元素，再将这些单词元素的长度累加并且每个单词之间还要算上空格的长度，接下来就检查这累加的长度什么时候会超过给定的max，如果超过的话，那么对于当前的这个right指向的就是恰好让累加长度大于max的这个单词元素，因此真正的right就应该是当前right的前一个单词；当确定了left和right之后，就应该对这个范围内的单词进行justify，首先应该检查left是否等于right，如果两者相等就说明，当前行只有一个单词，那么这一行的这个单词应该顶到左边，剩下的位置就应该是空格；接下来就应该检查right是否已经指向了给定String数组的最后一位元素，如果是那就说明不需要进行一般意义上的justify、而是让这个范围内的单词每一个都只空一个格子，后面的用空格补充完毕即可；然后计算一下left到right这个范围内的全部单词元素的总长度有多少，并且使用给定的max减去这个总长度，就算出来这一行应该有多少空格数量，然后根据这一行left到right的单词数算出一共有多少单词间隔，并且用空格数量除以单词间隔数量，就是每一个间隔应该放多少空格，最后用总空格数量对单词间隔数量取余，就是余下的单词间隔数，那么在把每个单词、每个间隔的空格数append到结果中时，都一个一个把这余下的单词间隔数加上，加完为止，这就完成了每一行的justify

65. Valid Number. 这个题目一位一位的分情况检查即可，对于一个valid的数字，只可能出现0到9的数字、dot、指数符号E和e、正负号，除此之外就可以立即判错；如果当前位置是dot，那么前面不能出现指数符号、不能出现另一个dot、如果当前dot是最后一个位置那么前面必须有数字；如果当前位置是指数符号E和e，那么前面不能出现指数符号、必须出现数字、指数符号不能出现在开头和结尾；如果当前位置是正负号，那么全部正负号数量不能超过2次、正负号不能出现在末尾、如果前面没有指数符号的话那么正负号必须出现在开头；另外要注意的是，根据以上逻辑，这里遍历给定字符串时，应该用传统的for循环，因为需要使用到当前位置的index

76. Minimum Window Substring. 首先建立一个Map，Map中的key表示s字符串出现的字符，value表示t字符串的字符数量：即所有出现在s中的字符在Map中都会有自己的key-value，而如果某一个字符也出现在t中的话，那么value就表示这个字符在t中出现的次数；题目需要通过一个i和一个j指针去维护sliding window，并且需要一个全局min长度变量和start索引记录全局最小的滑动窗口的起始位置，最后还需要一个count变量去记录当前t字符串中仍然未被滑动窗口圈定的字符数量；快指针往前走表示滑动窗口的扩展，每当快指针遍历到一个字符后，都需要把该字符在Map中进行数量更新减1，并且如果该字符在当前的Map中对应的value为正数的话，就说明当前滑动窗口扩展到了一个t字符串的字符，因此count就需要减1来表示当前少了一个未被滑动窗口圈定的字符；循环的过程需要检查count变量是否减少到0，因为这意味着所有t中的字符都已经被滑动窗口圈定了，这时就应该检查当前滑动窗口的长度和全局min长度比较，如果更优的话就应该更新全局的min和start位置，然后移动慢指针，每往前移动一个位置都意味着滑动窗口吐出了一个字符，那么对应在Map当中该字符的value就应该加1，而如果发现该字符的value加1以后大于0，这就意味着该字符是t中出现的字符（这是因为初始情况下Map中所有t中出现的字符value都大于0，而其他字符都小于0，随着滑动窗口的扩大、不存在于t中的字符的value只能被减少到负数、而存在于t中的字符会被减少到0），这时就应该更新count加1；最后根据找到的min和start，返回给定String的substring即可

30. Substring with Concatenation of All Words. 首先建立一个Map，key存储给定字符串数组的字符串、value存储这些字符串的出现次数；对给定字符串开始循环，对于每一个位置都作为起点，建立一个Map进行check，然后对给定字符串数组的长度进行循环，然后从当前位置开始获取到字符串的一个substring，检查该substring是否存在于预先建立的Map中，如果存在就put到checkMap中，并检查checkMap中包含的该substring的数量已经超过了预先建立的Map中的数量；检查完毕后，如果发现给定字符串数组已经全部遍历完毕，说明从当前位置开始往后取若干个substring已经完全涵盖了给定字符串数组的元素，因此就可以把这个位置加入到结果中

3. Longest Substring Without Repeating Characters. 比较典型的滑动窗口题目，首先maintain一个Map，key为字符value为出现次数，快慢指针圈定滑动窗口，快指针往前走，并且把每次指向的字符添加到Map当中；一旦当前字符出现重复、即在Map中的value大于1了，那么就应该移动慢指针，获取到慢指针指向的字符并且到Map中更新减1，然后慢指针往前移动；每次循环的最后应该更新全局结果，和快指针和慢指针圈定的窗口长度比较更新

6.14 做题

395. Longest Substring with At Least K Repeating Characters. 这个题目一定要注意，要保证被返回的substring中的每一个字符，在当前的这个substring中的重复频次一定要不小于k，而不是在全局的给定String中不小于k；因此这个题目的思路就变成了，使用双指针去遍历给定String，如果快指针往前走发现当前字符在当前String中频次小于k了，那么肯定这个字符就不能用了；但这时也不能简单的说从慢指针开始到快指针的前一个位置的这段substring就一定满足条件了，因为尽管这段部分的字符都通过了频次不小于k的检查，但那是在原本的String中频次不小于k、而不是在刚刚界定出来的这段部分的频次不小于k，因此对于慢指针开始到快指针的前一个位置这段substring，应该进行recursion操作重新检查在这个范围之内的结果；当recursion获取到结果后，再和res进行比较；接下来继续循环，慢指针就需要移动到快指针的后一个位置，然后快指针也往前走，开始重新计算

114. Flatten Binary Tree to Linked List. 这个题目的流程是这样：首先维护一个全局的prev节点，来记录flatten过程中的上一次操作的节点；检查当前root是否为null，不为null则依次对right和left子节点调用recursion方法；然后使得当前root的右子节点指向prev节点，而当前root的左子节点为null，这样就可以完成了这一次的flatten；最后更新prev为当前的root节点，以供下一次使用；这里prev节点的含义是上一次操作的root，而相比于当前的root来说，上一次操作的root也就是现在的prev，如果当前root和prev处于同一棵右子树（prev就是当前root的右子节点），那么不用变化；如果当前root和prev不处于同一棵右子树（当前root和prev是分叉的、prev不是root的右子节点而是左子节点、总之从root到prev不能靠右一条线走下来），但又因为prev是root的上一个操作节点故prev和root一定从顺序上讲是紧挨着的，那么这时使root的右子节点指向prev就意味着把root和prev这个地方给flatten了，因为prev之后的所有节点都是已经flatten过了的

222. Count Complete Tree Nodes. 这个题目要计算一个树的节点数量，对于一般的树来说计算节点数量只需要一个一个数出来就可以了，也就是各种遍历方法每遍历到一个节点都计数增加；但是对于这个完全二叉树来说，可以利用其特性进行简化计数；因为对于一个完全二叉树来说，最后一行以上都是满的，最后一行都是靠左排列的；因此就可以首先对给定的root进行左和右两个方向往下计数，看看它的左边和右边（严格一直往左走和有那个一直往右走）各自是多长；如果两边一样长就说明这个树整体是满的，因为最后一行总是靠左排列的，一样长就意味着最后一行的最右边也有节点，那么在这种情况下，这个树的节点数量就是1左移计算出来的边长数量减1即1 << length - 1（注意是1左移而不是边长左移），这是因为计算出的边长其实就相当于是这棵树的高度，而正常来讲一棵树的节点数应该是2的树高次方减1，那么对于1来说每左移一次都相当于乘2，那么左移树高次就相当于是2的树高次方；如果两边不一样长，那就各自对左子树和右子树进行recursion处理，最后两者结果只和再加当前root也就是1即可；这个题目利用完全二叉树的性质就在于，先算出左右两边长，如果一样则可以使用1的左移，从而减少了时间复杂度，因为1的左移是O(1)的时间

105. Construct Binary Tree from Preorder and Inorder Traversal. 根据preorder确定当前的root节点，然后根据这个root节点的值去inorder中找到左子树和右子树的范围，从而建立整个树；具体来说就是，对于preorder和inorder来说，preorder当前的第一个元素就一定是根节点，因为preorder遍历是先root遍历；而preorder的这个元素如果被放在inorder里的话就一定是中间，因为inorder是先左再中后右，而确定了root再inorder的位置以后，其左边就是左子树、右边就是右子树；所以需要创建一个Map，key为inorder的元素、value为inorder的index，从而方便根据preorder的元素去找到inorder的index，进而能够确定左右子树的范围；接下来通过recursion完成，每一次preorder的第一个元素就是root，然后去Map中找到inorder对应的index进而确定下一次recursion时的left和right的子树范围即可

106. Construct Binary Tree from Inorder and Postorder Traversal. 这个题目和上一题一样，只需要记住postorder是右边优先的preorder的逆转即可；因此首先建立起右边优先的preorder，然后recursion里面注意确定left和right的范围即可，因为当前的preorder也仍然是右边优先的

6.15 做题

116. Populating Next Right Pointers in Each Node. 这个题目使用recursion：首先检查base case就是，当前节点是否为叶节点，如果为叶节点直接返回当前节点即可；然后进行populating操作：对于当前root节点的左子节点，它的next就应该是当前root节点的右子节点；对于当前root节点的右子节点，它的next就应该是当前root节点的next的左子节点；这里可以看出，当前recursion所要解决的问题其实是当前root节点的左右子节点的next问题的，这就是为什么base case只需要检查当前节点是否为叶节点即可，因为叶节点没有左右子节点，并且recursion所返回的应该就是以当前root节点为根节点的子树，并且所有节点都已经完成populating了的；最后只需要对当前root节点的左右子节点都进行recursion操作，就相当于完成了左右子树的populating工作，然后返回root即可

117. Populating Next Right Pointers in Each Node II. 这个题目使用iteration方法进行行级遍历：设置一个dummy和一个cur，dummy的next每次都指向当前行的最左边，而cur则随着当前行进行遍历，注意当前行并不是root所在的行，而是root的子节点所在的行；对于当前的root，如果它不为空，则进一步去判断它的左子节点和右子节点是否为空，对于左子节点，如果不为空，则首先cur的next应该指向它，然后cur进一步也指向自己的next；对于右子节点，如果不为空，则首先cur的next也应该指向它，然后cur进一步也指向自己的next；讨论完毕左右子节点后，root再往自己的next走，这样等到下一次循环时，现在指向当前root.right的cur就可以连接到下一个root.left了，从而构建起next关系；而一旦root为null就说明到头了应该往下一行，那么由于dummy和cur都处在root的子节点的所在行，dummy还在最开始，因此root直接指向dummy，cur也重新指向dummy，dummy的next也指向空即可；最后返回原有的root；注意这里dummy本质上是通过cur去指向每一行开头的，因为cur本来指向dummy，而每一次行遍历时，首先cur的next指向当前行的第一个位置也就是当前root的left，那么这就相当于dummy的next指向了第一个位置，然后cur自己走了指向自己的next，dummy却没有走

96. Unique Binary Search Trees. 这个题目要知道如何构建DP，从1到n的每一个数字都可以作为根节点，比如k作为根节点，那么1到k-1就是左子树、k+1到n就是右子树，那么问题就被拆分成了k-1个元素和n - k个元素各自组成子树的个数，然后相乘，就是k为根节点的全部可能性；接下来从1到n自底而上进行构建DP即可；注意从k+1到n的右子树，虽然元素不同，但是组成子树的数量其实也是和从1到n-k是相同的

327. Count of Range Sum. 这个题目不太懂cache的意思，为什么在找到了k和j计算完之后还需要用cache去更新sums呢？https://leetcode.com/problems/co ... 0/Share-my-solution

289. Game of Life. 这个题目简单做个遍历就可以了，对于每一个位置都去看它周围的八个位置，除了越界的情况，检查每一个周围的位置是否为1，如果为1就计数；然后看看当前位置计数结果是多少，如果正好为3并且当前点是0表示死的，那么就把当前点设置为3表示去活；如果小于2或大于3并且当前点是1表示活的，那么就把当前点设置为2表示去死；最后遍历矩阵如果是2就变成0、3就变成1

6.16 做题

57. Insert Interval. 这个题目的思路是首先对整个给定二维区间数组遍历，对于内部每一个区间，首先检查其右端点：如果右端点比给定新区间的左端点还要小，则说明该区间和新区间肯定没有关系不会重合，因此对于这种区间来说可以直接加入到结果当中；当遇到某一个区间其右端点不再逼新区间的左端点小，就说明这个区间和新区间一定会有重合，而这种情况会随着对区间的遍历、一直持续到某一个区间的左端点比给定新区间的右端点大，则说明该区间和新区间肯定没有重合，因此这种情况涵盖了：区间左端点 < 新区间左端点 < 区间右端点 < 新区间右端点，新区间左端点 < 区间左端点 < 区间右端点 < 新区间右端点，新区间左端点 < 区间左端点 < 新区间右端点 < 区间右端点，直到新区间左端点 < 新区间右端点 < 区间左端点 < 区间右端点才算没有重合，因此在区间左端点不大于新区间右端点之前，都算重合；那么对于重合的情况，就应该进行重新计算，计算这部分每一个区间的左端点和新区间的左端点比较哪一个更小、计算这部分每一个区间的右端点和新区间的右端点比较哪一个更大，最后这部分区间挨个和新区间比较会得到一个最小的左端点和最大的右端点，这两个端点组成的新区间就是重合操作后的区间，加入到结果中；然后对于随后的遍历直接全部加到结果中即可；要注意的是，这个题目要返回一个二维数组，但是在添加结果集的时候应该使用List，从而才能添加；在第二部分的重合操作中，每个区间和新区间的端点比较，把记录的最大最小区间更新到新区间中即可

56. Merge Intervals. 这个题目要合并重叠的区间；思路很简单，一个一个遍历给定的区间，对于当前区间来说，和它下一个区间进行比较，如果发现和下一个区间有重合的话那么当前区间就应该和下一个区间合并，然后再去检查再往后的一个区间，直到发现当前区间和下一个区间不重合，那么就可以往后检查、对下一个区间进行同样的操作了；这个题目在具体实现上需要注意，如何保持当前区间的检查和更新、如何往后检查对下一个区间进行同样的操作？首先应该将给定区间数组排好序，上述思路的基础就是建立在给定区间已经排序的基础上；然后先将第一个区间加入到结果中，并且使用一个引用reference指向该区间；然后进行遍历，对于每一个区间，都去跟当前区间比较是否重合，而当前区间就是当前reference指向的区间，重合判断的标准就是reference指向的当前区间的右端点、是否比被遍历的区间的左端点要大于或等于，如果是这样那么就进行重合操作，也就是对reference指向的当前区间和被遍历的区间的右端点取最大值，并且用这个最大值更新reference指向的当前区间；而一旦发现不重合、即reference指向的当前区间右端点小于被遍历的区间的左端点，那么首先由于reference指向的当前区间实际上已经存在于结果中了，因此reference直接指向被遍历到的这个新的不重合的区间，然后把这个区间再加入到结果中；通过这种操作，被遍历到的新区间就成了当前区间，而reference也指向它，就可以在随后的遍历中重复以上所有操作了

352. Data Stream as Disjoint Intervals. 这个题目的核心是使用TreeMap，去获取当前添加的数字所对应的与它相邻的前面和后面的区间，然后进行分类讨论检查是否需要合并；首先建立一个TreeMap作为给定类的成员变量并且在构造函数中初始化，然后在添加数字元素的方法中，首先检查TreeMap是否包含该数字，如果包含则说明该数字的添加并不能造成什么影响、故直接返回即可；然后从TreeMap中获取比当前数字小的最大的key和比当前数字大的最小的key，也就是相邻的两区间；这里注意TreeMap的key是每一个区间的左端点，value则是这个区间；获取到以后分四种情况检查：1、当前添加的val正好处于前后两个区间之间并紧挨着，即lowerKey所对应的区间的右端点正好比给定val小1，higherKey所对应的区间的左端点正好比给定val大1，那么lowerKey和higherKey所对应的区间就可以合并，新区间就是lowerKey区间左端点和higherKey区间右端点所圈定的区间，新区间添加到TreeMap中，key就是lowerKey；2、当前添加的val可能可以拓展前一个区间的右端点，即lowerKey区间的右端点+1大于等于当前的val，对于这种情况就使用lowerKey区间的左端点作为左端点、lowerKey区间的右端点与给定val相比更大的那个作为右端点，组成的新区间添加到TreeMap中key就是lowerKey；3、当前添加的val可以拓展后一个区间的左端点，即当前添加的val正好等于higherKey区间的左端点-1，那么就拓展该区间，使得该区间的左端点等于给定的val，并且将对应的key换成val、原有的higherKey移除；4、以上情况都不属于，那么就单独添加进TreeMap即可；最后需要获取区间时，就依次取出key对应的value区间即可

239. Sliding Window Maximum. 这个题目有两种方式，正常一点的方式是使用一个顺序队列存储index，遍历给定数组，对于每一个元素的index都添加进队列中，但是添加之前需要对队列进行一些操作：首先如果队列非空且队列头部所存储的index已经在window之外了（因为window是往后移动的，因此当前遍历的i减去k再加1就是当前window的最左端，比这个最左端还要小那么这个index就在window之外），那么就应该把这个index给poll出去；而如果队列的尾部所存储的index所对应的给定数组元素，其值要小于或等于当前遍历到的数组元素，那么就应该把这个index给poll出去（这里操作的是队列尾部，所以应该pollLast），这是因为在当前的window范围内已经存在了一个靠后的元素（即当前元素）比靠前的元素（即队列尾部存储的index对应的给定数组元素）还要大，而这个window往后sliding的过程中靠前的那个元素肯定先被poll出去，因此这个靠前的元素是不可能在接下来称为窗口最大元素了，它的存在就没有了意义，因此应该被poll出去，对这个操作进行重复直到队列从后往前找到了一个较大的元素；接下来就可以把该元素所对应的index添加到队列中了；然后还需要进行检查，如果当前遍历到的index足够大以至于从0到它已经可以组成一个完整的window了（i - k + 1 >= 0），那么就应该把当前队列的头部存储的index所对应的给定数组元素，添加到结果当中；这是因为通过以上从队列中剔除以及增加index的操作，可以保证当前队列头部元素是当前window的最大值：通过第一步的poll把窗口之外的index给poll了出去、通过第二步的pollLast把比当前窗口的最后一个元素小的元素都pollLast了出去，而在往后遍历的过程其实就是window移动的过程，这两个poll的步骤可以保证在window移动的过程队列中总是会有最大的那个index，因为元素在每一次遍历时都在不断的跟当前遍历元素进行比较并且不断往外poll

295. Find Median from Data Stream. 这个题目维护两个Heap，maxHeap存储小的那一部分、minHeap存储大的那一部分，让两个Heap的size最多相差一位，从而届时获取median是只需要讨论两个Heap的peek即可；当添加元素时，如果两个Heap均为空则随意添加，如果两个Heap的size相同则根据Heap的peek和给定元素的大小进行判断，如果minHeap的size更大则检查给定元素是大是小，如果是大则应该添加到minHeap但这样其size就过大了，因此需要让minHeap去poll出来一个最小的给maxHeap来offer，然后再将给定元素offer进minHeap中，而如果元素是小则直接添加到maxHeap即可；对于maxHeap的size更大的情况，作相同讨论