Stack性质
定义
Stack的定义便是先进后出,在python中用list实现
1 | class Stack(object): |
Basic 题目
225. Implement Stack using Queues
只用一个queue,每次append的时候,都要把前面的给pop出来再append进去
1 | class MyStack(object): |
232. Implement Queue using Stacks
用两个stack来存,输出的时候再全部放入到output的stack中
1 | class MyQueue(object): |
20. Valid Parentheses
左边的Parentheses作为key进入,右面的来判断是不是跟顶部的一样
1 | class Solution(object): |
42. Trapping Rain Water
这道题感觉不是十分好想,需要维持一个stack来进行操作,当遇到新加的元素比栈顶元素大的时候,我们就要比较之前的元素,如果栈里面是有一个,则不能形成坑,continue;不然就比较之前的元素和当前的最小值,减去高度。哎呀,还是需要画图用例子来说比较好
我们的做法是,遍历高度,如果此时栈为空,或者当前高度小于等于栈顶高度,则把当前高度的坐标压入栈,注意我们不直接把高度压入栈,而是把坐标压入栈,这样方便我们在后来算水平距离。当我们遇到比栈顶高度大的时候,就说明有可能会有坑存在,可以装雨水。此时我们栈里至少有一个高度,如果只有一个的话,那么不能形成坑,我们直接跳过,如果多余一个的话,那么此时把栈顶元素取出来当作坑,新的栈顶元素就是左边界,当前高度是右边界,只要取二者较小的,减去坑的高度,长度就是右边界坐标减去左边界坐标再减1,二者相乘就是盛水量啦
http://www.cnblogs.com/grandyang/p/4402392.html
1 | class Solution(object): |
Decreasing stack
递减stack主要是记录数组中第一个比它大的数
1 | while stack and nums[i] > stack[-1]: |
496. Next Greater Element I
1 | class Solution(object): |
739. Daily Temperatures
1 | class Solution(object): |
503. Next Greater Element II
1 | class Solution(object): |
316. Remove Duplicate Letters
1 | class Solution(object): |
稍难题
84. Largest Rectangle in Histogram
维持一个递增stack,碰到一个比栈顶元素小的数,不断比较,更新最大面积
1 | class Solution(object): |
85. Maximal Rectangle
同样的操作,只是这次是把上一道题的高度,变成矩阵中连续长度
1 | class Solution(object): |