课程3：stack，deque，heap的运用
Expression Expand：利用stack来记录暂不需要的信息
Trapping Rain Water： 找到每个点的左边最大和右边最大
Implement Queue by Two Stacks： stack的简单应用
Min Stack：stack的简单应用
Sliding Window Median：因为python无法直接删除heap里的元素，所以用lazy pop来解决
Trapping Rain Water II ：用heap从四周朝中间找
Maximal Rectangle：这题是那道最大rectangle的扩展，把每一行作为底边来考虑当前行可以形成的最大矩形的大小
Max Tree：stack保持单调性的应用
Largest Rectangle in Histogram：保持单调递增，就可以知道以当前长度为高的矩形的左右边界了，stack里存的是index
Data Stream Median：直接用两个heap，比较简单
Sliding Window Maximum：用一个deque保持window里递减
Binary Tree Maximum Path Sum II：简单的dfs
Heapify：对一半的值执行一个siftdown操作，从len/2开始一直操作到0，这样就可以使得最小值移动到最上面，并且保证每个值的2i和2i+1的节点都比当前值要大
K Edit Distance：比较粗糙的做法是用动态规划找出每个单词到target的edit distance然后和k比较下
Expression Tree Build：利用stack找出左右节点
Convert Expression to Reverse Polish Notation：比较麻烦的地方在于确定每一个运算符的base
课程4：按值二分和扫描线
Sqrt(x)：比较基础的按值二分
Maximum Average Subarray：这题的按值二分比较神奇，判定条件有点麻烦
Sqrt(x) II：同样的按值二分，只是循环结束条件是start和end小于某个微小的数
Number of Airplanes in the Sky：很简单的扫描线问题
Divide Two Integers ：又一道用二分法思想的题
Find Peak Element：二分法基本题
First Bad Version：又一道基本题
Find Peak Element II：在matrix找到peak，每次可以丢掉左边或者右边，或者是上边和下边
Wood Cut：比较简单的按值二分，判定条件是把每一个都除一下，看看要多少刀
Find the Duplicate Number：二分法，判定条件是数一数比它小的值的个数
Smallest Rectangle Enclosing Black Pixels：按照给出的pixels向上下左右二分，找到边界
网友评论