【leetcode】数组
1. 769. Max Chunks To Make Sorted
思路
遍历数组。维持一个max，表示当前数组应维持的最小的i，如果arri大于max，就更新max为arri，然后如果i==max，也就说i已经到达最小要求，就cnt++，且max更新为数组下一个位置的值。
技巧度：B，思维绕脑度：B+
主要是对arri, i 和max的关系情况分类的切入点要准。
详情
https://cloud.tencent.com/developer/article/1432275
2. 714. Best Time to Buy and Sell Stock with Transaction Fee
思路
动态规划，维持两个状态数组：卖出状态和持有状态
技巧度：C，思维绕脑度：C
3. 48. Rotate Image
思路
用i和offset结合，i代表第i行(0<= i <= (n-1)/2), offset是从i开始的偏移。
技巧度：C，思维绕脑度：A-
i和offset的取值范围要想对。做的时候想错了很多次......希望下次做到的时候能更快速准确。
4. 39. Combination Sum
思路
回溯。
技巧度：C，思维绕脑度：C
是回溯算法的初级应用。
5. 729. My Calendar I
思路
用Map<int, int>，<int, int>的含义是<start, end>解决即可
技巧度：C，思维绕脑度：C
6. 873. Length of Longest Fibonacci Subsequence
思路
参考https://www.youtube.com/watch?v=Py3Jj0M1McY
技巧度：B，思维绕脑度：C
主要难点是想到用二维dp来解决问题
7. 870. Advantage Shuffle
思路
用priority_queue<pair<int, int>>解决。使用贪心算法，按数组A从大到小尽可能在数组B中找到匹配的元素即可。就像是“田忌赛马”一样，让A的上等马去应付B的中等马，依次类推，就能有尽可能多的匹配对数。
技巧度：C, 思维绕脑度：C
贪心算法
详情
代码见：https://cloud.tencent.com/developer/article/1432156
关于自定义priority_queue的比较，见https://blog.csdn.net/bat67/article/details/77585312
8. 731. My Calendar II
思路
imos
9. Number of Matching Subsequences
思路
map + 二分查找
10. 11. Container With Most Water
贪心双指针
11. 73. Set Matrix Zeroes
https://www.youtube.com/watch?v=T-_ZdgvO-oU
12. Construct Binary Tree from Preorder and Inorder Traversal
思路
确定inorder数组的中间index时，不可使用lower_bound，要遍历查找
13. 209. Minimum Size Subarray Sum
思路
滑动窗口。当窗口右侧伸展到[a, b, c, d, e]时，可以得知：(a + b + c + d + e) > k且(a + b + c + d) <= k，所以，以b、c、d、e中任何一个为开头的窗口和，要想大于k，其右端至少要在e处（否则如果在d处，则(b + c + d) < (a + b + c + d) <= k)。
14. 56. Merge Intervals
思路
imos，注意区间为a,a时的处理：如果a,a包含在别的区间内，就合并。如果是单独出现的，就单独放置该区间。处理方法是，如果在确定起始边界时，发现当前变化数为0，则该区间是a,a区间，直接放置即可。
15. 376. Wiggle Subsequence
维持up和down两个变量，记录以上升沿/下降沿为最后一个沿的最小长度
16. 16. 3Sum Closest
固定一个数，则问题降阶为另外两个数用双指针从头尾向中间遍历。问题简化为杨氏矩阵。
17. 31. Next Permutation
https://yq.aliyun.com/articles/863
思路
假设有一个数：
abcd...hi...wxyz
从i到z递减，且h小于i。
我们的任务是找到一个排列比它大，且尽可能小。
那么如果要找一个比它大的数，这个数的第一位不同必须在h上。下面用反证法证明：
- 如果该位在h以前，也就是abc...一直到h之前，那么这个数一定比 在h位上不同的数要大。
- 如果该位在h之后，也就是i...wxyz，那就说明i位之前的数都是一样的，没有交换过。而i...wxzy是递减的，在局部上本来就是数最大的排列，任何交换都无法使它更大。所以也不可能在h之后。
所以该位在h上。那么h要与谁交换呢？这个数肯定要比h大，但又要尽可能小。所以就在h右侧寻找比它大又尽可能小的数。将他们交换。然后剩下的数就从左到右，从小到大排序，就可以得到结果了。
详情
https://cloud.tencent.com/developer/article/1432264
18. 79. Word Search
思路
回溯。我果然还是有丶东西的。
19. 152. Maximum Product Subarray
思路
dp。维护两个变量: max_to_cur和min_to_cur，另外再维护一个max_global变量即可