leetcode-26- 删除排序数组中的重复项-java
1 考虑到leetcode测试用例，数组为空和长度为1的情况。
2 java队列最后一个的索引为长度-1，不能用arr[length]。
3 可以认为这个方法是双指针
数组完成排序后，我们可以放置两个指针 i 和index，其中i 是慢指针，而 index 是快指针。只要 nums[i]=nums[index-1]，我们就增加i以跳过重复项。
当我们遇到 nums[index-1]≠nums[i]时，跳过重复项的运行已经结束，因此我们必须把它的值复制到 index。然后递增index和i，接着我们将再次重复相同的过程，直到i 到达数组的末尾为止。

leetcode-122-买卖股票的最佳时机 II-java
1 有时候数组循环处理，从前往后很麻烦，从后往前很简单
2 我们可以简单地继续在斜坡上爬升并持续增加从连续交易中获得的利润，而不是在谷之后寻找每个峰值。最后，我们将有效地使用峰值和谷值，但我们不需要跟踪峰值和谷值对应的成本以及最大利润，但我们可以直接继续增加加数组的连续数字之间的差值，如果第二个数字大于第一个数字，我们获得的总和将是最大利润。这种方法将简化解决方案。

leetcode-189-旋转数组（ Rotate Array）-java
1 使用一个大小为k的数组，保存0-k-1位的数字，然后将k到length-1位的数字按照index=(i+k) mod length 为新位置摆放，然后将temp数组放入新位置
2 因为反转用的空间只用一个变量即可（或者不用也行，使用位运算即可）
将数组分为两部分，分为0——length-k-1和length-k——length-1; 两部分分别反转，再整体反转，就能得到正确的结果。 例子：[1,2,3,4,5,6,7] 和 k = 3 分为[1,2,3,4]和[5,6,7];分别反转后得到[4,3,2,1,7,6,5] 再整体反转得[5,6,7,1,2,3,4] 即为正确得结果
每个数原来应该在的位置是(i+k) mod length
0——length-k-1 就是 length-k-i 再反转 k+i
length-k——length-1 就是 length*2-k-i ,再反转 k+i-length
这两个就是(i+k) mod length

nums = “----->–>”; k =3
result = “–>----->”;
reverse “----->–>” we can get “<–<-----”
reverse “<–” we can get “–><-----”
reverse “<-----” we can get “–>----->”

如果需要额外空间的（移动x位的），可以考虑多次反转

方法一中使用额外数组的原因在于如果我们直接将每个数字放至它最后的位置，这样被放置位置的元素会被覆盖从而丢失。因此，从另一个角度，我们可以将被替换的元素保存在变量temp中，从而避免了额外数组的开销。
我们从位置0开始，最初令temp=nums[0]。根据规则，位置0的元素会放至(0+k) mod n的位置，令x=(0+k) mod n，此时交换temp和nums[x]，完成位置x的更新。然后，我们考察位置x，并交换temp和nums[(x+k) mod n]，从而完成下一个位置的更新。不断进行上述过程，直至回到初始位置0。
容易发现，当回到初始位置0时，有些数字可能还没有遍历到，此时我们应该从下一个数字开始重复的过程，可是这个时候怎么才算遍历结束呢？我们不妨先考虑这样一个问题：从0开始不断遍历，最终回到起点0的过程中，我们遍历了多少个元素？

由于最终回到了起点，故该过程恰好走了整数数量的圈，不妨设为a圈；再设该过程总共遍历了b个元素。因此，我们有an=bk，即an一定为n和k的公倍数。又因为我们在第一次回到起点时就结束，因此a要尽可能小，故an就是n,k的最小公倍数lcm(n,k)，因此b就为lcm(n,k)/k。
这说明单次遍历会访问到lcm(n,k)/k个元素。为了访问到所有的元素，我们需要进行遍历的次数为gcd(n,k)
其中gcd指的是最大公约数。
如果读者对上面的数学推导的理解有一定困难，也可以使用另外一种方式完成代码：使用单独的变量 count 跟踪当前已经访问的元素数量，当 count=n时，结束遍历过程。

leetcode-217-存在重复元素(Contains Duplicate)-java
有时候考虑到重复，可以采用set数据结构
重复的时候，有时候可以使用计数排序的思想，创建一个新数组来计数
这个方法按道理，时间复杂度和set是一样的，还要遍历两次，但是之所以快，可能是hashset内部操作虽然是O(1),但是又几部操作，比计数排序每位只做三个操作慢

leetcode-136-只出现一次的数字(single number)-java
面对重复的问题，如果对空间有限制，可以考虑位运算，尤其是亦或，而且位运算往往很巧妙，速度很快
异或,xor
(a^b) ^b=a ,而且满足交换律

leetcode-350-两个数组的交集 II( Intersections of two arrays II)-java
1 如果数组中元素重复的有多个，可以考虑用map装起来，key为数组中的数，对应的value为数的个数
2 可以采用排序的算法，先用array的方法排序，再使用双指针算法比较，
相等则加入list，两个指针各自向后移1位
哪个小，就小的对应指针向后移1位
速度比之前快，主要是如果一方的长度很小，有可能可以很快算完（一方结束即可）
3 计数排序在面对重复的问题，可以一定程度上代替hashmap，但是计数排序的长度为max-min+1，如果max-min是int的max和min，得到的长度会超过int，成为负数，因为java中数组的长度最大是int的max，不能超过它

leetcode-66-加一(PLUS one)-java
注意for循环到最后一个时，那个i++,i–也要执行一次，执行完才让i不符合范围。
新建一个1000型的数组（新建后，设置1就可以，之后不用设置0，因为创建是就为0）
判断+1进位可以用mod10

leetcode-283-移动零（remove zeroes）-java
1 如果在程序中每次循环都要操作一个东西，可以试试在最后一次性一块操作。
2 将所有 0 移动到数组末尾。
所有非零元素必须保持其原始顺序。
这里很好地认识到这两个需求是相互排斥的，也就是说，你可以解决单独的子问题，然后将它们组合在一起以得到最终的解决方案。
这种方法即先满足一个需求，然后满足另一个需求。它以一种巧妙的方式做到了这一点。上述问题也可以用另一种方式描述，“将所有非 0 元素置于数组前面，保持它们的相对顺序相同”。
3 当我们遇到一个非零元素时，我们需要交换当前指针和慢速指针指向的元素，然后前进两个指针。如果它是零元素，我们只前进当前指针。

leetcode-1-两数之和（two sum）-java
如果要查找数组中某个值和值的index的话，可以先把数组，以值为key，index为value，插入hashmap，要的时候map.get（值）

leetcode-36- 有效的数独(valid sudoku)-java
查找数组中重复数字，可用
hashmap（如果数字很多，需要index）
hashset（如果数字很多，不需要index）
计数排序（数字要在一定范围内，不能超过integer.max_value,要几个，用int[],只要一个，用boolean[]）
位运算（只能算出重复1个）（如果只用一个int，数字浮动在0-32之内），相当于BitMap，这个可以范围很大

九宫格，先算出左上角顶点，然后for循环i 3次，j 3次。（正推）
如何算出顶点，第一个for循环indexi 3次（每次+3），indexj也一样。
或者k从0循环9次，indexi =(k%3)3;indexj=k-begini/3;
或者从i，j倒推*第几个九宫格， box_index = (row / 3) * 3 + columns / 3（直接设置9个数组，遍历81个元素，直接放入对应数组。）

leetcode-48-旋转图像（rotate image）-java
对于矩阵，图像旋转等位置变化的问题，最关键的要点就是每个点具体位置变化的点，从哪里来，到哪里去
解决这个问题，
首先可以考虑对称的方法，针对某个关键点或者关键的线进行对称
如果找不到对称的方法，可以具体考虑点变化的规律，可以找到几个实例点，研究前后位置的变化
还可以将绝对坐标与相对坐标进行转化，研究针对某个点的坐标变化

leetcode-384-打乱数组(shuffle an array)-java
在class中设置一个int数组作为源头，一个int数组作为打乱的数组返回
reset方法，返回一个copy的数组
shuffle方法，将打乱的数组再次打乱后返回，
Fisher-Yates 洗牌算法跟暴力算法很像。在每次迭代中，生成一个范围在当前下标到数组末尾元素下标之间的随机整数。接下来，将当前元素和随机选出的下标所指的元素互相交换 - 这一步模拟了每次从 “帽子” 里面摸一个元素的过程，其中选取下标范围的依据在于每个被摸出的元素都不可能再被摸出来了。此外还有一个需要注意的细节，当前元素是可以和它本身互相交换的 - 否则生成最后的排列组合的概率就不对了。

leetcode-15-三数之和(3sum)-java
解法1：
数组排序后，先确定两个数，再从set中确定是否有对应的第三个数
设置set，将所有的数字都放入set。
然后将数组排序。
先计算，两个负数，一个正数的情况，双指针计算完所有的负数的情况，根据set是否有对应正数来确定是否组合存在。
再计算两个正数，一个负数的情况。这时，注意三个0的情况
解法2：
先确定一个数，再从排序后的数组从头到尾，双指针，确定是否有两个数的和为对应的数
首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L]和 nums[R]，计算三个数的和 sum判断是否满足为 0，满足则添加进结果集
如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环
如果 nums[i] =nums[i?1]，则说明该数字重复，会导致结果重复，所以应该跳过
当 sum=0 时，nums[L]= nums[L+1] 则会导致结果重复，应该跳过，L++
当 sum= 0 时，nums[R]= nums[R?1]则会导致结果重复，应该跳过，R??

leetcode-73- 矩阵置零(set matrix zeroes)-java
使用固定的空间，原地算法

其实我们可以利用首行首列来表示这一行，这一列有没有出现0，于此同时，需要使用2个额外的变量，来标记首行和首列是否需要置0.因此大致思路是：
1、扫描首行和首列，记录其是否需要置0，
2、扫描第二行，第三行。。。，如果出现0了，那么在对应的首行和首列标记设置0
3、当遍历完后，根据标记的数据回过去，将对应的行和列置0.

leetcode-334- 递增的三元子序列(increasingly triplet subsequence)-java
3个连续递增子序列
有3个槽位，a,b,c
满足条件 a < b < c，即可
需要将合适的元素填入这3个槽位
比如说：
one=10，two=20，
如果现在n>20,直接成功，
10<n<=20,two=n,
n<10,one=n （这里是重点），假设n=5，此时one=5，two=20，然后下一步，
如果n<5,与之前一样，设置one=n，
如果20>n>5,设置two=n，此时递增数列是顺序的，one=5，two=15，比之前的10和20都小，而且是two在one后
如果n>20,成功，因为尽管现在的one在two的后面，但是n比在前面的two大，
而每一个two都有一个比它小的，而且在two前面的one（在这里的一开始的10），（这句话很重要！！！！）
此时10,20，n，成为递增序列

leetcode-380-常数时间插入、删除和获取随机元素(Insert Delete GetRandom O(1))-java
这道题让我们在常数时间范围内实现插入删除和获得随机数操作，如果这道题没有常数时间的限制，那么将会是一道非常简单的题，我们直接用一个set就可以搞定所有的操作。但是由于时间的限制，我们无法在常数时间内实现获取随机数，所以只能另辟蹊径。此题的正确解法是利用到了一个一维数组和一个哈希表，其中数组用来保存数字，哈希表用来建立每个数字和其在数组中的位置之间的映射，对于插入操作，我们先看这个数字是否已经在哈希表中存在，如果存在的话直接返回false，不存在的话，我们将其插入到数组的末尾，然后建立数字和其位置的映射。删除操作是比较tricky的，我们还是要先判断其是否在哈希表里，如果没有，直接返回false。由于哈希表的删除是常数时间的，而数组并不是，为了使数组删除也能常数级，我们实际上将要删除的数字和数组的最后一个数字调换个位置，然后修改对应的哈希表中的值，这样我们只需要删除数组的最后一个元素即可，保证了常数时间内的删除。而返回随机数对于数组来说就很简单了，我们只要随机生成一个位置，返回该位置上的数字即可，参见代码如下：

leetcode-238- 除自身以外数组的乘积(Product of Array Except Self)-java
要的结果就是每个数 左边的数的乘积 * 右边的数的乘积
建立数组res，首先第一个循环，p就是i的左边的数的乘积，res的每个值=p，就是i的左边的数的乘积。
然后下一个循环，q就是 i的右边的数（包括i）的乘积，然后res[i-1]=res[i-1]q=左边的数的乘积右边的数的乘积

leetcode-54-螺旋矩阵-java
解法1（成功，0ms，极快）
最外层所有元素按照顺时针顺序输出，其次是次外层，以此类推。
我们从左上方开始以顺时针的顺序遍历所有元素，假设当前层左上角坐标是(rowBegin,colBegin)，右下角坐标是 (rowEnd,colEnd)
上面横线(rowBegin,colBegin)到(rowBegin,colEnd) 从左到右
右边竖线(rowBegin+1,colEnd)到(rowEnd-1,colEnd) 从上到下
下面横线(rowEnd,colEnd)到(rowEnd,colBegin) 从右到左
左边竖线(rowEnd-1,colBegin)到(rowBegin+1,colBegin) 从下到上
每次输出最外一层后，begin++，end–
解法2（别人的）
绘制螺旋轨迹路径，我们发现当路径超出界限或者进入之前访问过的单元格时，会顺时针旋转方向。
假设数组有 R行 C列，seen[r][c]表示第 r 行第 c 列的单元格之前已经被访问过了。当前所在位置为 (r, c)，前进方向是 di。我们希望访问所有 R x C 个单元格。
当我们遍历整个矩阵，下一步候选移动位置是 (cr, cc)。如果这个候选位置在矩阵范围内并且没有被访问过，那么它将会变成下一步移动的位置；否则，我们将前进方向顺时针旋转之后再计算下一步的移动位置。

leetcode-454-四数相加 II-java
题目说0<=N<=500
1.如果采用暴力解法O(n^4)
500^4=62500000000 这样计算机承受不了
2.利用查找表将D放入查找表中 遍历A、B、C在查找表中找是否存在-A、-B、-C
这样的话时间复杂度为O(n^3)
500^3=125000000还是太大了
3.如果能将其化解为O(n^2)的算法
500^2=250000这样是可以接受的
故只需要将C+D的每一种可能放入查找表（map）
这样我们只需要寻找这个表里面有没有-A-B就行了
有的话则A+B+C+D=0，然后统计一下个数
将数组C，D 任意组合的和存入查找表中， key是和，value 是出现的次数。记录A，B 任意组合的和的负值，然后在查找表中查找是否有对应的值
时间复杂度：O(n^2）。

leetcode-011-盛最多水的容器-java
这种方法背后的思路在于，两线段之间形成的区域总是会受到其中较短那条长度的限制。此外，两线段距离越远，得到的面积就越大。
我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。 此外，我们会使用变量 maxarea 来持续存储到目前为止所获得的最大面积。
在每一步中，我们会找出指针所指向的两条线段形成的区域，更新 maxarea，并将指向较短线段的指针向较长线段那端移动一步。
最初我们考虑由最外围两条线段构成的区域。现在，为了使面积最大化，我们需要考虑更长的两条线段之间的区域。
如果我们试图将指向较长线段的指针向内侧移动，矩形区域的面积将受限于较短的线段而不会获得任何增加。
但是，在同样的条件下，移动指向较短线段的指针尽管造成了矩形宽度的减小，但却可能会有助于面积的增大。因为移动较短线段的指针会得到一条相对较长的线段，这可以克服由宽度减小而引起的面积减小。
由于面积取决于边长短的那一端假设为m，所以要想得到比当前更大的面积，边长短的那一端必须舍弃，因为如果不舍弃，高最大就是m，而随着指针的移动宽会一直减小，因此面积只会越来越小。

leetcode-289-生命游戏-java
简单直白，完全按照题目解释做了两个循环。第一个循环用于标记，第二个循环用于赋值。
1——保持1
-1——1转0
0——保持0
-2——0转1

原地算法的两种思路：
首先，原地算法的妨碍是改变一个值 x 从a变成b，但是改变后别人还需要a这个值。
方法1：改变时，把a变成特殊字符，如a_b，既有a的特征，也有b的特征，最后统一把a_b改成b。
方法2：改变时，安装题目的性质，使用少量的额外空间，记录a或b，按照特定顺序进行改变。

leetcode-041-缺失的第一个正数-java
方法1：
将负数，零的数替换为 Integer.MAX_VALUE 。
目前所有数都是正数，让nums[now-1]变成负数
遍历数组。当读到数字 now 时，如果now - 1小于length，替换第 now - 1 个元素的符号。（从正号变成负号）
注意重复元素：只能改变一次符号。
再次遍历数组。返回第一个正数元素的下标。
如果 nums[i] > 0，则返回 i + 1 。（下标为i，代表数字i + 1）
如果之前的步骤中没有发现 nums 中有正数元素，相当于nums[0-length-1] 对应数字1-length都全了，则返回length + 1。
方法2：
如图所示：我们可以把数组进行一次“排序”，“排序”的规则是：如果这个数字 i 落在“区间范围里”，i 就应该放在索引为 i - 1 的位置上，下面具体解释。
1、数字 i 落在“区间范围里”；
例如：[3, 4, -1, 1]，一共 4 个数字，那么如果这个数组中出现 “1”、“2”、“3”、“4”，就是我们重点要关注的数字了；
又例如：[7, 8, 9, 11, 12] 一共 5 个数字，每一个都不是 “1”、“2”、“3”、“4”、“5” 中的一个，因此我们无须关注它们；
2、i 就应该放在索引为i - 1 的位置上；
这句话也可以这么说 “索引为 i 的位置上应该存放的数字是 i + 1”。
[3, 4, -1, 1]变成[1, -1, 3, 4]
就看上面那张图，数字 1 应该放在索引为 0 的位置上，数字 3 应该放在索引为 2 的位置上，数字 4 应该放在索引为 3 的位置上。一个数字放在它应该放的位置上，我们就认为这个位置是“和谐”的，看起来“顺眼”的。
按照以上规则排好序以后，缺失的第 1个正数一下子就看出来了，那么“最不和谐”的数字的索引 +1，就为所求。那如果所有的数字都“和谐”，数组的长度 +1就为所求。

注意：如果题目限制了空间复杂度，可以考虑对参数进行破坏性的修改，将需要的数据放到参数中。

leetcode-128-最长连续序列-java
哈希表和线性空间的构造
这个优化算法与暴力算法仅有两处不同：这些数字用一个 HashSet 保存，实现 O(1) 时间的查询，同时，我们只对 当前数字 - 1 不在哈希表里的数字，作为连续序列的第一个数字去找对应的最长序列，这是因为其他数字一定已经出现在了某个序列里。
尽管在 for 循环中嵌套了一个 while 循环，时间复杂度看起来像是二次方级别的。但其实它是线性的算法。因为只有当 currentNum 遇到了一个序列的开始， while 循环才会被执行（也就是 currentNum-1 不在数组 nums 里）， while 循环在整个运行过程中只会被迭代 n 次。这意味着尽管看起来时间复杂度为 O(n?n)，实际这个嵌套循环只会运行 O(n+n)=O(n) 次。所有的计算都是线性时间的，所以总的时间复杂度是 O(n)的。

leetcode-287-寻找重复数-java
解法1（别人的）
二分法
按题目表达，设数组长度为n，则数组中元素∈[1,n?1]，且只有一个重复元素。一个直观的想法，设一个数字k∈[1,n?1]，统计数组中小于等于k的数字的个数count：
若count<=k，说明重复数字一定在(k,n?1]的范围内。
若count>k，说明重复数字一定在[0,k]的范围内。
利用这个性质，我们使用二分查找逐渐缩小重复数字所在的范围。
初试化左右 数字 边界left=1,right=n?1
循环条件left<right:
mid=(left+right)/2
按照性质，统计数组中小于等于mid的元素个数count
若 count<=mid，说明重复数字一定在(mid,right]的范围内。令left=mid+1
若count>mid，说明重复数字一定在[left,mid]的范围内。令right=mid。
返回left

解法2（别人的）
快慢指针
分为两步：
找到环
找到环的入口（即重复元素）
找环：
定义快慢指针slow=0,fast=0
进入循环：
slow每次走一步，即slow=nums[slow]
fast每次走两步，即fast=nums[nums[fast]]
当slow= =fast时，退出循环。
当快慢指针相遇时，一定在环内。此时假设slow走了k步，则fast走了2k步。设环的周长为c，则k%c= =0。
找环的入口：
定义新的指针find=0
进入循环：
find每次走一步，即find=nums[find]
slow每次走一步，即slow=nums[slow] 当两指针相遇时，即find==slow，返回find
为何相遇时，找到的就是入口：
假设起点到环的入口(重复元素)，需要m步。此时slow走了n+m步，其中n是环的周长c的整数倍，所以相当于slow走了m步到达入口，再走了n步。所以相遇时一定是环的入口。

leetcode-239-滑动窗口最大值-java
解法1：
将输入数组分割成有 k 个元素的块。
若 n % k != 0，则最后一块的元素个数可能更少。
开头元素为 i ，结尾元素为 j 的当前滑动窗口可能在一个块内，也可能在两个块中。
情况 1 比较简单。 建立数组 left， 其中 left[j] 是从块的开始到下标 j 最大的元素，方向 左->右。
为了处理更复杂的情况 2，我们需要数组 right，其中 right[j] 是从块的结尾到下标 j 最大的元素，方向 右->左。right 数组和 left 除了方向不同以外基本一致。
两数组一起可以提供两个块内元素的全部信息。考虑从下标 i 到下标 j的滑动窗口。 根据定义，right[i] 是左侧块内的最大元素， left[j] 是右侧块内的最大元素。因此滑动窗口中的最大元素为 max(right[i], left[j])。

解法2
优先队列
对于「最大值」，我们可以想到一种非常合适的数据结构，那就是优先队列（堆），其中的大根堆可以帮助我们实时维护一系列元素中的最大值。
对于本题而言，初始时，我们将数组 nums 的前 k 个元素放入优先队列中。每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组 nums中的位置出现在滑动窗口左边界的左侧。因此，当我们后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，我们可以将其永久地从优先队列中移除。
我们不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组 (num,index)，表示元素 num 在数组中的下标为 index。

解法3
单调队列
我们可以顺着方法一的思路继续进行优化。
由于我们需要求出的是滑动窗口的最大值，如果当前的滑动窗口中有两个下标 i 和 j，其中 i 在 j 的左侧（i<j），并且 i 对应的元素不大于 j 对应的元素（nums[i]≤nums[j]），那么会发生什么呢？
当滑动窗口向右移动时，只要 i 还在窗口中，那么 i 一定也还在窗口中，这是 i 在 j 的左侧所保证的。因此，由于 nums[j] 的存在，nums[i] 一定不会是滑动窗口中的最大值了，我们可以将 nums[i] 永久地移除。

因此我们可以使用一个队列存储所有还没有被移除的下标。在队列中，这些下标按照从小到大的顺序被存储，并且它们在数组 nums 中对应的值是严格单调递减的。因为如果队列中有两个相邻的下标，它们对应的值相等或者递增，那么令前者为 i，后者为 j，就对应了上面所说的情况，即 nums[i] 会被移除，这就产生了矛盾。
当滑动窗口向右移动时，我们需要把一个新的元素放入队列中。为了保持队列的性质，我们会不断地将新的元素与队尾的元素相比较，如果前者大于等于后者，那么队尾的元素就可以被永久地移除，我们将其弹出队列。我们需要不断地进行此项操作，直到队列为空或者新的元素小于队尾的元素。

由于队列中下标对应的元素是严格单调递减的，因此此时队首下标对应的元素就是滑动窗口中的最大值。但与方法一中相同的是，此时的最大值可能在滑动窗口左边界的左侧，并且随着窗口向右移动，它永远不可能出现在滑动窗口中了。因此我们还需要不断从队首弹出元素，直到队首元素在窗口中为止。
为了可以同时弹出队首和队尾的元素，我们需要使用双端队列。满足这种单调性的双端队列一般称作「单调队列」。

leetcode-315-计算右侧小于当前元素的个数-java
归并排序法
归并排序将序列先分成两个相同长度的子序列，分别排序后，再归并两个有序的子序列。
在归并排序的过程中，顺便完成个数统计。
关键在于归并操作。
例如：[-1, 5, -5, -5, -4, -2, -3, 5, 2, -5] N=10
分成： [ -1, 5, -5, -5, -4 ] [ -2, -3, 5, 2, -5]
假设已经将子序列排好序后，并且每个元素的右侧比其小的个数都求出来了。
左边 的结果
0 1 2 3 4
-5 -5 -4 -1 5
0 0 0 3 3
右边的结果
5 6 7 8 9
-5 -3 -2 2 5
0 1 2 1 2
我们看最后一步归并。
A[0] = -5 <= A[5] = -5 取结果T[0] = A[0]
A[1] =-5 <= A[5] = -5 取结果T[1] = A[1]
A[2] =-4 > A[5] = -5 取结果T[2] = A[5]
A[2] = -4 < A[6] = -3 取结果T[3] = A[2]，但是A[2]右边比A[2]小元素的个数要加上 第二个子序列中 A[6]前 的元素个数1. COUNTS[3] = 0 + 1 =1。
为什么？
因为取A[2]表示在第二个子序列中A[6]之前的元素都小于A[2]，因此一定要加上。
A[3] = -1 > A[6] = -3 取结果T[4] = A[6]
A[3] = -1 > A[7] = -2 取结果T[5] = A[7]
A[3] = -1 < A[8] = 2 取结果T[6] = A[3] COUNTS[6] = 3 + 3 =6。第二个3表示 在第二个子序列中A[8]之前的小于A[3] 的个数。
A[4] = 5 > A[8] = 2 取结果T[7] = A[8]
A[4] = 5 <= A[9] = 5 取结果T[8] = A[4] COUNTS[4] = 3 + 4 =7。第二个4表示 在第二个子序列中A[9]之前的小于A[4] 的个数。
取结果T[9] = A[9] 。
从上面的可看出，在归并操作中，当取第一个子序列中的元素a时，为其增加第二个子序列中比a小的元素个数。
但是要强调一个case。
例如:[2,1,2]
我们知道其结果是[1,0,0].
如果在排序的过程中第一个2和第二个2交换了位置，那么最终结果是[0,0,1]。这显然是错误的。
这要求排序算法必须是稳定的。而归并排序是稳定的。
因此，本算法不会出现上述的问题。
但是，实际上为了将下标与元素和个数绑定起来，方便计数。
在数字数组A上又加了层索引数组W。归并排序过程中，元素顺序的调整，只会修改索引数组W。

leetcode-295-数据流的中位数-java
我们需要明确，对于此题而言，找到median就意味着，我们可以将此数据流分为两部分，即第一部分值全部小于median（or =），第二部分值全部大于median（or =）。
所以我们用maxheap存第一部分，并按照倒序存放；minheap来存第二部分，并按照顺序排放。

我们先立下一个约定，即maxheap总比minheap多一个，方便于我们之后进行查找。这样一来，初始第一个值就加入maxheap。
比较即将加入进heap的数字与两个堆堆顶的数字，若大于maxheap，则需要放进minheap中。
在后面陆续的增加中，我们只需保持两个heap size之间的关系，不断进行调节即可。

关于查找，那就只有两个地方可以找到median：如果是奇数，median肯定在maxheap的堆顶，直接输出即可；若是偶数，我们需要取出两个堆各自的堆顶元素，取其均值，再输出。

leetcode-406-根据身高重建队列-java
让我们从最简单的情况下思考，当队列中所有人的 (h,k) 都是相同的高度 h，只有 k 不同时，解决方案很简单：每个人在队列的索引 index = k。
即使不是所有人都是同一高度，这个策略也是可行的。因为个子矮的人相对于个子高的人是 “看不见” 的，所以可以先安排个子高的人。
我们先安排身高为 7 的人，将它放置在与 k 值相等的索引上；再安排身高为 6 的人，同样的将它放置在与 k 值相等的索引上。
该策略可以递归进行：

将最高的人按照 k 值升序排序，然后将它们放置到输出队列中与 k 值相等的索引位置上。
按降序取下一个高度，同样按 k 值对该身高的人升序排序，然后逐个插入到输出队列中与 k 值相等的索引位置上。
直到完成为止。

leetcode-42-接雨水-java
5种解法，按行，按列，动态规划，双指针，栈
https://blog.csdn.net/xushiyu1996818/article/details/107223665

leetcode-218-天际线问题-java
归并算法或者大顶堆
https://blog.csdn.net/xushiyu1996818/article/details/107250559

leetcode-84-柱状图中最大的矩形-java
https://blog.csdn.net/xushiyu1996818/article/details/107361318

leetcode-31-下一个排列-java
顺序 1234 1243 1324 1342 1423 1432 2134 2143 2314
可以看到，每次往下一个的改变，都是先从倒数第二个数往前遍历i，然后从末尾（倒数第一个）到i+1的方向遍历j，如果有nums[j]>nums[i]，则将i与j互换，然后排序i之后的所有元素，从小到大。
如果没有找到i与j，说明这个数已经是最大的了，元素排序是从大到小，只需所有元素从小到大排序即可

如1234 1243，4是第一个大于3的，互换1243，然后排序4后面的元素，还是1243
1432 2134，2<3,3<4,3<4,2是第一个大于1的，互换，2431，然后排序2后面的元素，2134

leetcode-438-找到字符串中所有字母异位词-java
解法1（成功，7ms，较快）
滑动窗口算法，数组array代表26个字符对应的个数，首先对于子串p，每个元素对array[p.charAt(i)-‘a’]++，num初始为p的length
对于串s，一个窗口大小为p的length，进入则array[now-‘a’]–,出去则++,如果是有效的字符，则修改num，如果num为0，说明全部匹配，加入result

解法2（别人的）
本题是典型的窗口滑动+左右索引指针的算法
一开始还是先将字符串转换为字符数组，定义一个ans来接收结果
这里使用了两个数组needs和window来分别记录需要得到的元素和滑动窗口遍历到的元素
首先把目标数组arrP中有的元素都放入needs中，然后通过不断移动滑动窗口将目标元素的个数保存到window中
如果window数组中记录的元素个数超过了needs数组的元素个数，则开始移动左窗口慢慢减少多余的个数
最后把整个遍历过程中所有符合要求的左窗口索引放到ans中并返回即可。

leetcode-448-找到所有数组中消失的数字-java
原地修改
我们需要知道数组中存在的数字，由于数组的元素取值范围是 [1, N]，所以我们可以不使用额外的空间去解决它。
我们可以在输入数组本身以某种方式标记已访问过的数字，然后再找到缺失的数字。

遍历输入数组的每个元素一次。
我们将把 |nums[i]|-1 索引位置的元素标记为负数。即 nums[nums[i]?1] × ?1
然后遍历数组，若当前数组元素 nums[i] 为负数，说明我们在数组中存在数字 i+1。