Stack 算法题的思考

这类题目也是比较多的，一般比较繁琐。思路类似DFS，不过可以不使用递归实现。

String 解析类

这类比较多的就是计算器，以及分析括号里的内容。例如解析 3[a]2[bc],这时候就可以在遇到[的时候把之前的东西都压到栈里，之后当遇到]的时候把内容再pop出来。

对于计算器，如果是后缀表达式的话，可以把结果都压到栈里，遇到运算符再pop出运算。有括号的话还是按括号的方法，主要要注意加法和乘法的区别。

计算器系列最重要的思想就是前一个符号看作大小的指示，之后那个才用来做计算。例如(1+2)+(3+4), +可以看作是是后一个括号的符号。对于1*2 + 6/3,原理相同。在进行+6/3的时候，先把sign变成+6，并进行除法标记。之后再用除法。

大小差距

还有一类题目就是问下一个比自己大的数还有多远，可以使用栈。栈里面存的都是比栈顶小的数，遇到比栈顶大的数n就可以弹出栈里的数j，因为这时我们可以知道比之前那个数j大的数在n了，更新之前那个数j的结果。

栈的作用存一个至今遇到的大值。栈底是最大的值，栈顶是至今遇到的大值里最小的。

for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
        int idx = stack.pop();
        res[idx] = i - idx;
    }
        stack.push(i);
}
//保存自己是最低的边界 
for (int i = 0; i < N; ++i) {
    while (!stack.isEmpty() && A[i] <= A[stack.peek()])
                stack.pop();
    prev[i] = stack.isEmpty() ? -1 : stack.peek();
    stack.push(i);
    }