【leetcode】栈
1. 895. Maximum Frequency Stack
思路 要想到用多个stack来解决问题，如下图所示构建数据结构
- 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，不断化简问题，最后求得答案。
3. 856. Score of Parentheses
思路 用一个stack<int>解决问题。用-2表示左括号，-1表示右括号（事实上-1没用上）。 遇到左括号就放入-2（左括号）。 遇到右括号就把栈内的数依次取出，直到遇到-2（左括号）。如果中途没有遇到-2以外的其它数字，就把1放入栈；否则，把取出来的数求和，乘以2，放回栈中。 最后要记得把栈中的数取出求和。
4. 94. Binary Tree Inorder Traversal
思路 用一个stack<TreeNode *>解决问题。先尽可能往左地把节点放入栈。 每次取出节点并访问，再对它的右节点尽可能往左地放入栈即可。
5. 907. Sum of Subarray Minimums
思路 有两种做法，用数组或者increasing stack
6. 331. Verify Preorder Serialization of a Binary Tree
思路 有几种思路：
- 用非叶节点和叶节点的入度与出度的特征判断
- 用“空位”判断。叶节点会占用一个空位，非叶节点占用一个空位后会多出两个空位。
- 我的思路则是：把它看成程序的一次递归调用，非“#”字符代表函函数的递归调用，“#”代表调用函数并返回了值。每个非“#”字符都应当调用两次递归函数，再返回自己的返回值（返回一个“#"）。最终如果只剩下“#”说明函数正常返回。
我对这个的理解是： 剩余的可放置字符空位按照先序排序。 每次遇到一个字符，就把它放置在剩余空位的第一个（按照先序顺序中的第一个）。 因此，在放置过程中，空位不应当用尽。且把所有字符放置完成时，所有空位应当用尽。
7. 853. Car Fleet
思路 把车按离终点的距离从远到近排列。 车队的到达时间取决于排在最前面的那辆车。 从远到近遍历车辆，如果上一辆车到达终点的时间比这一辆车快，就合并把上一辆车合并到当前车队里。然后把当前车队放入栈。 最后，栈里面的元素数量就是车队数量。
思路 采用贪婪原则，从后往前遍历数组，维持一个从栈底到栈顶的递减栈，让s2尽可能地大（这样找到s1 < s2时就可以返回true了）。 所以s2的寻找分两步：
- 找到一个s2
- 尽可能地让s2变大
算法 从后往前遍历数组，维持一个从栈底到栈顶的递减栈。 每次遇到一个数，如果比栈顶大，就循环把栈顶弹出，并且把s2设置为最后弹出的数（因为维护的是递减栈，最后弹出的数是比当前数小的数中最大的，也就是说，它是s2的最佳候补）。 由于s2每次都被设置为被弹出的数，而且这些数字都比新栈顶小，可以发现，栈里的元素都比s2大，也是遍历过的数中比s2大的所有数，且其中至少有一个数是可以作为s3的（这一段助于理解，意思是栈内的数包含了s2的所有候补）。 也就是说，当s2被设置/更新的时候，一定已经找到了一个s3（至于是多少并不重要）。所以我们如果遇到某个数小于s2，就说明找到了s1，就可以返回true了。所以在遍历的过程中我们主要做2件事：
- 设置/更新s2
- 寻找s1
9. 402. Remove K Digits
思路 从前往后遍历数字，如果某一位的数字比下一位大，说明只要删除这一位，让下一位数字来代替这一位，就可以让整个数字变小。
所以维护一个非递减栈，从前向后遍历每一位，循环把比当前位大的栈顶弹出，直到k的次数用尽，或者栈弹光了。再把当前位放进栈里面。 遍历以后，如果给的k足够大，栈里的元素从栈底到栈顶，应当是非递减排列的。 如果还有剩余的k的次数，就高位往低位删除数字（因为高位的数字比较大。同样位数的数字中，位数越低，就应当放置越小的数字，而把大的数字留在高位）。 最后删除前导“0”。 另外补充个细节：如果全部字符删除掉了，说明答案是0，就返回“0”。