刷题记录帖子

173 Binary Search Tree Iterator

其实最简单的就是直接 in-order 遍历，简单方便。但是初始化效率较差。

然后的好方法就是，用 stack 来做，参考这个帖子, https://maxming0.github.io/2020/ ... arch-Tree-Iterator/。

941 Valid Mountain Array

我是做了一次遍历的两个阶段，

看了这个解答, https://maxming0.github.io/2020/12/10/Valid-Mountain-Array/ ，居然还有双指针这个解法，

391        Perfect Rectangle

暴力解有无 overlap 在 Python 会超时，所以跳出来，还是参考了这个 weixin 文章求解的，https://mp.weixin.qq.com/s/PL7h_5hx6XZ1hEyVVusRBA 不过我发现花花的算法更好，https://www.youtube.com/watch?v=8JM_dyOu_JY

花花的解法也是巧妙，其实和我用的是一样的，只是 C++ 可以简化代码，显得他的解法更好，

补充内容 (2020-12-11 13:53):
这题目，居然还有一种做法，扫描线法。

补充内容 (2020-12-11 13:53):
https://mp.weixin.qq.com/s?__biz ... 32f4&scene=2...

54        Spiral Matrix

参考 59 的解法，这个其实还是很简单的，不过在程序的处理的时候，需要关注 edge cases。

885. Spiral Matrix III

写的时候，还是绕进去了，参考了这个视频，https://www.youtube.com/watch?v=Vqv1iQQ2n_s

这个题目最大的关键在于要看出来步长的规律，是  1，1，3，3，5，5 的规律增加，所以其实每个步长都可以简化成 curr_step //2 + 1,然后每次循环后 curr_step +1

同时，这里的越界需要正确理解，其实不妨碍任何结果，你只需要不断实现 spiral 就行，最后总会返回去的，因为 sprial 就是转了一圈，必定回去。
参考这个图，理解下为什么，其实就是虚拟的那些 cell 不需要记录，想象这个 matrix 可以无限延伸的话，其实整个情况没啥变化。

然后就是我们可以很简单地写出代码，情况真的很简单。

977 Squares of a Sorted Array

简单题，不是暴力做的 NlogN 就用 Two pointer + Merge Sort

98 Validate Binary Search Tree

深刻反省下，虽然做过这道题目还是没 bug free。

最后的调用函数的返回值，应该 check both returns from left branch and right branch。

880 Decoded String at Index

正向做是常规思路，但是会 TLE，所以 backward 做是最好的。官方解析很好，https://leetcode.com/problems/decoded-string-at-index/solution/

一个优化是，直接 break 累加，参考这个帖子，https://maxming0.github.io/2020/12/20/Decoded-String-at-Index/

LC 1539 Kth Missing Positive Number

很巧妙的思想就是发现如何 表示截止每个 index missing 的 number 数目，很简单，但是需要直觉，其实是 ind - arr[ind] - 1.

然后题目转化为 二分搜索，需要注意，这里 left 和 right 有一个 cross over，所以答案是 left + k, 简单而且优雅，但是思维过程并不简单。很考验水平。参考这个帖子，https://www.bilibili.com/video/BV1QK4y1p7E3

3. 无重复字符的最长子串 OK