stack

基础知识

• 如何实现一个可以支持push，pop，getmin的栈？使用两个栈，一个栈维护当前最小值。和存数据的栈同步更新

题目选讲

• Editor
  • 题意：模拟打字操作，有insert，left，right，delete操作，然后query x，问前x数中最大的前项和是多少，x小于当前光标所在处
  • 题解：维护两个栈，表示当前光标左边的数和右边的数有哪些，同时维护当前光标之前前项和和最大前项和
  • 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/hdoj4699.cpp
• Largest Rectangle in a Histogram
  • 题意：给出n个宽度为1的矩阵，顺序摆放，问能组成的最大的矩阵面积是多少
  • 题解：先思考一个问题，如果矩阵的高度是单调递增，那么最大的矩阵面积就是尝试以每个矩阵的高度作为最终矩形的高度，那么如果由一个比上一个小怎么办，如果比上一个小，那之前高的那些都没用了，因为即便后面有更高的，也因为当前这个短板，无法使用。所以中间那部分压缩一下就行，直接跳过。维护一个单调递增的栈。
  • 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/poj2559.cpp