DarkAlexWang's Blog
0%

Stack总结

Posted on Edited on In Views: Valine:
Symbols count in article: 5k Reading time ≈ 5 mins.

Stack性质

定义

Stack的定义便是先进后出，在python中用list实现

1
2
3
4
5
6
7
8
9
10
11
12
class Stack(object):
	def __init__(self):
		self.stack = []
	def push(self, i):
		self.stack.append(i)
	def pop(self):
		if self.stack：
			return self.stack.pop()
		else:
			raise("Error")
	def peek(self):
		return self.stack[-1]

Basic 题目

225. Implement Stack using Queues

只用一个queue，每次append的时候，都要把前面的给pop出来再append进去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class MyStack(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.queue = []
        

    def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: void
        """
        self.queue.append(x)
        size = len(self.queue)
        while size > 1:
            self.queue.append(self.queue.pop(0))
            size -= 1      

    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        :rtype: int
        """
        return self.queue.pop(0)
        

    def top(self):
        """
        Get the top element.
        :rtype: int
        """
        return self.queue[0]
        

    def empty(self):
        """
        Returns whether the stack is empty.
        :rtype: bool
        """
        return len(self.queue) == 0
        
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

232. Implement Queue using Stacks

用两个stack来存，输出的时候再全部放入到output的stack中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MyQueue(object):
    def __init__(self):
        self.input = []
        self.output = []
        
    def push(self, x):
        self.input.append(x)

    def pop(self):
        self.peek()
        return self.output.pop()
        
    def peek(self):
        if(self.output == []):
            while(self.input != []):
                self.output.append(self.input.pop())
        return self.output[-1]
        
    def empty(self):
        return self.input == [] and self.output == []

20. Valid Parentheses

左边的Parentheses作为key进入,右面的来判断是不是跟顶部的一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        for char in s:
            if char == '(':
                stack.append(')')
            elif char == '[':
                stack.append(']')
            elif char == '{':
                stack.append('}')
            elif not stack or char != stack.pop():
                return False
        return not stack

42. Trapping Rain Water

这道题感觉不是十分好想，需要维持一个stack来进行操作，当遇到新加的元素比栈顶元素大的时候，我们就要比较之前的元素，如果栈里面是有一个，则不能形成坑，continue；不然就比较之前的元素和当前的最小值，减去高度。哎呀，还是需要画图用例子来说比较好

我们的做法是，遍历高度，如果此时栈为空，或者当前高度小于等于栈顶高度，则把当前高度的坐标压入栈，注意我们不直接把高度压入栈，而是把坐标压入栈，这样方便我们在后来算水平距离。当我们遇到比栈顶高度大的时候，就说明有可能会有坑存在，可以装雨水。此时我们栈里至少有一个高度，如果只有一个的话，那么不能形成坑，我们直接跳过，如果多余一个的话，那么此时把栈顶元素取出来当作坑，新的栈顶元素就是左边界，当前高度是右边界，只要取二者较小的，减去坑的高度，长度就是右边界坐标减去左边界坐标再减1，二者相乘就是盛水量啦
http://www.cnblogs.com/grandyang/p/4402392.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        stack = []
        i = 0
        size = len(height)
        res = 0
        while i < size:
            if not stack or height[i] <= height[stack[-1]]:
                stack.append(i)
                i += 1
            else:
                top = stack.pop()
                if not stack:
                    continue
                else:
                    res += (min(height[i], height[stack[-1]]) - height[top]) * (i - stack[-1] -1) # height * width
        return res

Decreasing stack

递减stack主要是记录数组中第一个比它大的数

1
2
3
while stack and nums[i] > stack[-1]:
	dic[stack.pop()] = nums[i]
stack.append(nums[i])

496. Next Greater Element I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def nextGreaterElement(self, findNums, nums):
        """
        :type findNums: List[int]
        :type nums: List[int]
        :rtype: List[int]
        """
        res = []
        stack = []
        # to store
        dic = dict()
        for i in range(len(nums)):
            while stack and nums[i] > stack[-1]:
                dic[stack.pop()] = nums[i]
            stack.append(nums[i])
        # deal with last   
        while stack:
            dic[stack.pop()] = -1
            
        for i in range(len(findNums)):
            res.append(dic[findNums[i]])
        return res

739. Daily Temperatures

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        res = [0] * len(temperatures)
        stack = []
        left = 0
        for i in range(len(temperatures)):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                index = stack.pop()
                res[index] = i - index
            stack.append(i)
        return res

503. Next Greater Element II

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    # stack
    def nextGreaterElements(self, nums):
        stack, res = [], [-1] * len(nums)
        for i in range(len(nums)) * 2:
            while stack and (nums[stack[-1]] < nums[i]):
                res[stack.pop()] = nums[i]
            stack.append(i)
            
        return res

316. Remove Duplicate Letters

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def removeDuplicateLetters(self, s):
        """
        :type s: str
        :rtype: str
        """
        stack = []
        dic = dict()
        for char in s:
            dic[char] = dic.get(char, 0) + 1
            
        for char in s:
            dic[char] -= 1
            if char in stack:
                continue
            else:
                while stack and ord(char) < ord(stack[-1]) and dic[stack[-1]] > 0:
                    stack.pop()
            stack.append(char)
        return "".join(stack)

稍难题

84. Largest Rectangle in Histogram

维持一个递增stack，碰到一个比栈顶元素小的数，不断比较，更新最大面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        res = 0
        stack = []
        for i in range(len(heights)+1):
            height = heights[i] if i!= len(heights) else 0
            while stack and height <= heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i - stack[-1] -1 if stack else i
                res = max(res, h*w)
            stack.append(i)
        return res

85. Maximal Rectangle

同样的操作，只是这次是把上一道题的高度，变成矩阵中连续长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def maximalRectangle(self, matrix):
    	# O(m^2)
        if not matrix or not matrix[0]:
            return 0
        n = len(matrix[0])
        # init heights array 
        height = [0] * (n + 1)
        ans = 0
        # calculate each row
        for row in matrix:
            for i in range(n):
                # count next level '1'
                height[i] = height[i] + 1 if row[i] == '1' else 0
                
            stack = []
            
            for i in range(n + 1):
                while stack and height[i] <= height[stack[-1]]:
                    h = height[stack.pop()]
                    # if not stack means left boundary is zero then width is i else is the stack[-1] index
                    w = i - 1 - stack[-1] if stack else i
                    ans = max(ans, h * w)
                stack.append(i)
        return ans