Leetcode 中stack在string处理中的应用

1. Valid Parentheses
这题思路较简单。用stack保存考察的char如果是右括号就对比和栈顶元素是否匹配，是则弹出否则插入。

2. Longest Valid Parentheses
这道题由于要求长度，因此压入栈的不是字符本身，而是index。遇到（直接压入，遇到）如果栈非空而且栈顶是（则update当前最大长度。 3. Simplify Path 预处理：去掉多余的"/"并在最后一位补上“/”。 设置状态位 flag==1 说明一层目录的开始，flag==2是一层目录的结尾。注意区别 "/."和“/..”. 前者直接舍弃，后者需要把栈顶元素弹出
4. Largest Rectangle in Histogram
最简单的方法就是依次遍历，取最大值 O（n^2）。比较巧妙的算法是用一个stack，存直方图的index，如果下一个直方图比栈顶直方图高，继续压栈，否则计算下一个直方图和当前直方图组成的面积。 5. Maximal Rectangle
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area. 此题第一步先纵向累计，i.e. 新建matrix (called mat), mat[i][j] 表示第j列上 以i结尾的最长连续1的个数。此步结束可以得到i组直方图然后用上题思路求解 6. Evaluate the value of an arithmetic expression in Reverse Polish Notation.
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
思路很简单， 读出来如果是操作数就压栈，如果是操作符，就把栈顶的两个元素拿出来计算，结果再次压栈