1. 895. Maximum Frequency Stack
思路
要想到用多个stack来解决问题，如下图所示构建数据结构
参考
https://www.bilibili.com/video/av31145075/
相关问题
- problem 146
- problem 460
2. 880.Decoded String at Index
思路
用size表示在i处，字符串进行解码后的长度。
如果有一个解码后的字符串为appleappleappleappleappleapple，且K=24，那么答案相当于在字符串apple中求K = 4的字符。即size=26,K=24的问题可转化为size=5，K=4的问题。
利用这一点可以先找到刚好size>=K的位置，再反向遍历S，不断化简问题，最后求得答案。
详情
https://www.jianshu.com/p/6844792b938f
3. 856. Score of Parentheses
思路
用一个stack<int>解决问题。用-2表示左括号，-1表示右括号（事实上-1没用上）。
遇到左括号就放入-2（左括号）。
遇到右括号就把栈内的数依次取出，直到遇到-2（左括号）。如果中途没有遇到-2以外的其它数字，就把1放入栈；否则，把取出来的数求和，乘以2，放回栈中。
最后要记得把栈中的数取出求和。
详情
https://www.jianshu.com/p/1dccac87d350
4. 94. Binary Tree Inorder Traversal
思路
用一个stack<TreeNode *>解决问题。先尽可能往左地把节点放入栈。
每次取出节点并访问，再对它的右节点尽可能往左地放入栈即可。
详情
https://www.jianshu.com/p/fd16978c7b1a
5. 907. Sum of Subarray Minimums
思路
有两种做法，用数组或者increasing stack
详情
https://www.jianshu.com/p/8273168bab07
6. 331. Verify Preorder Serialization of a Binary Tree
思路
有几种思路：
- 用非叶节点和叶节点的入度与出度的特征判断
- 用“空位”判断。叶节点会占用一个空位，非叶节点占用一个空位后会多出两个空位。
- 我的思路则是：把它看成程序的一次递归调用，非“#”字符代表函函数的递归调用，“#”代表调用函数并返回了值。每个非“#”字符都应当调用两次递归函数，再返回自己的返回值（返回一个“#"）。最终如果只剩下“#”说明函数正常返回。
详情
https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/152593/Atypical-Java-5ms-O(1)-space-approach
这个是以占位思路解题的。
我对这个的理解是：
剩余的可放置字符空位按照先序排序。
每次遇到一个字符，就把它放置在剩余空位的第一个（按照先序顺序中的第一个）。
因此，在放置过程中，空位不应当用尽。且把所有字符放置完成时，所有空位应当用尽。
7. 853. Car Fleet
思路
把车按离终点的距离从远到近排列。
车队的到达时间取决于排在最前面的那辆车。
从远到近遍历车辆，如果上一辆车到达终点的时间比这一辆车快，就合并把上一辆车合并到当前车队里。然后把当前车队放入栈。
最后，栈里面的元素数量就是车队数量。
详情
https://www.jianshu.com/p/e23605210c50
8. 456. 132 Pattern
思路
采用贪婪原则，从后往前遍历数组，维持一个从栈底到栈顶的递减栈，让s2尽可能地大（这样找到s1 < s2时就可以返回true了）。
所以s2的寻找分两步：
- 找到一个s2
- 尽可能地让s2变大
算法
从后往前遍历数组，维持一个从栈底到栈顶的递减栈。
每次遇到一个数，如果比栈顶大，就循环把栈顶弹出，并且把s2设置为最后弹出的数（因为维护的是递减栈，最后弹出的数是比当前数小的数中最大的，也就是说，它是s2的最佳候补）。
由于s2每次都被设置为被弹出的数，而且这些数字都比新栈顶小，可以发现，栈里的元素都比s2大，也是遍历过的数中比s2大的所有数，且其中至少有一个数是可以作为s3的（这一段助于理解，意思是栈内的数包含了s2的所有候补）。
也就是说，当s2被设置/更新的时候，一定已经找到了一个s3（至于是多少并不重要）。所以我们如果遇到某个数小于s2，就说明找到了s1，就可以返回true了。所以在遍历的过程中我们主要做2件事：
- 设置/更新s2
- 寻找s1
详情
https://www.jianshu.com/p/92cb3a44c4b2
9. 402. Remove K Digits
思路
从前往后遍历数字，如果某一位的数字比下一位大，说明只要删除这一位，让下一位数字来代替这一位，就可以让整个数字变小。
所以维护一个非递减栈，从前向后遍历每一位，循环把比当前位大的栈顶弹出，直到k的次数用尽，或者栈弹光了。再把当前位放进栈里面。
遍历以后，如果给的k足够大，栈里的元素从栈底到栈顶，应当是非递减排列的。
如果还有剩余的k的次数，就高位往低位删除数字（因为高位的数字比较大。同样位数的数字中，位数越低，就应当放置越小的数字，而把大的数字留在高位）。
最后删除前导“0”。
另外补充个细节：如果全部字符删除掉了，说明答案是0，就返回“0”。
详情
https://www.jianshu.com/p/32f368d25c1f
