Leetcode题解 - 栈和队列

Posted on | Post modified: | In
Words count in article: 3.6k

本系列为Leetcode刷题笔记，刷题平台为Leetcode中文站， 刷题按Tag分类。本系列题解汇总如下 (持续更新…)：

本文主要是栈和队列相关题目题解总结。

[TOC]

栈和队列

栈的顺序为后进先出，队列 的顺序为先进先出。

20. 有效的括号

题目描述

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

1
2
输入: "()"
输出: true

示例 2:

1
2
输入: "()[]{}"
输出: true

示例 3:

1
2
输入: "(]"
输出: false

示例 4:

1
2
输入: "([)]"
输出: false

示例 5:

1
2
输入: "{[]}"
输出: true

解题思路

使用栈，遍历字符串，当栈为空或者当前字符为左括号’(‘,’[‘,’{‘时或者为右括号但是栈顶字符与其不匹配，则将字符加入栈，否则栈顶字符出栈。最后判断栈是否为空。

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

71. 简化路径

题目描述

以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径

请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。

示例 1：

1
2
3
输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。

示例 2：

1
2
3
输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。

示例 3：

1
2
3
输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：

1
2
输入："/a/./b/../../c/"
输出："/c"

示例 5：

1
2
输入："/a/../../b/../c//.//"
输出："/c"

示例 6：

1
2
输入："/a//b////c/d//././/.."
输出："/a/b/c"

解题思路

将字符串按照‘/‘分隔得到了每个文件的目录，然后遍历每个目录进行入栈或者出栈。
如果目录为空或者为当前目录’.’，则不进行任何操作；如果为’..’，表示返回上一级目录，如果栈中有上级目录，则将其弹出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def simplifyPath(self, path):
        """
        :type path: str
        :rtype: str
        """
        if not path:
            return '/'
        stack = []
        path = path.split('/')
        for c in path:
            if not c or c == '.':
                continue
            if c == '..':
                if stack:
                    stack.pop()
            else:
                stack.append(c)
        return '/'+'/'.join(stack)

84. 柱状图中最大的矩形

题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10

解题思路

使用一个递增单调栈，栈中保存坐标，数组中坐标依次入栈，当当前坐标的值小于栈顶坐标的值，则栈顶坐标弹出，并计算弹出坐标的面积，它的右边界是当前坐标的值（因为当前坐标让它出栈），左边界是栈顶坐标（当栈为空时为-1）。
当数组遍历完成后，栈不为空，则依次弹出，计算弹出坐标的面积，右边界是数组长度，左边界是栈顶坐标（当栈为空时为-1）。

例如：[2,1,5,6,2,3]
先将2的坐标入栈，栈为[0]；
元素1的坐标1入栈前比较，因为1位置的元素比栈顶(0)位置的元素小，则位置0出栈，栈为空，计算0位置的面积(1-(-1)-1)*2=2，在将1入栈，栈为[1]；
坐标2的元素5大于栈顶位置元素(1)，则坐标2入栈，栈为[1,2]；
坐标3的元素6大于栈顶位置元素(5)，则坐标3入栈，栈为[1,2,3]；
坐标4的元素2小于栈顶位置元素(6)，则将栈顶位置3弹出，栈为[1,2]，计算3位置的面积(4-2-1)*6 = 6，此时2依然小于栈顶位置2的元素5，则栈顶位置2出栈，栈为[1]，计算2位置的面积(4-1-1)*5=10；此时2大于栈顶位置元素，则2的坐标4入栈，栈为[1,4]；
坐标5的元素3大于栈顶位置元素(2)，坐标5入栈，栈为[1,4,5]；
数组遍历完成。

此时栈不为空，依次弹出计算面积。
弹出位置5，栈为[1,4]，面积为(6-4-1)*3=3;
弹出位置4，栈为[1]，面积为(6-1-1)*2=8;
弹出位置1，栈为空，面积为(6-(-1)-1)*1=6;
所以最大面积为max(2,6,10,3,8,6)=10。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """

        if len(heights) == 0:
            return 0
        res = 0
        stack = []
        for i in range(len(heights)):
            while stack and heights[i] < heights[stack[-1]]:
                index = stack.pop()
                left = stack[-1] if stack else -1
                res = max(res, (i-left-1)*heights[index])
            stack.append(i)

        while stack:
            index = stack.pop()
            left = stack[-1] if stack else -1
            res = max(res, (len(heights) - left - 1)*heights[index])

        return res

85. 最大矩形

题目描述

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例:

1
2
3
4
5
6
7
8
输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

解题思路

使用一个辅助数组，大小为矩阵列宽，依次以矩阵每一行为底计算最大面积，直接调用上一题的代码计算。辅助数组计算方法：初始化为0，当当前元素为1是，高度加1，为0时直接为0。
例如上例：
第一行 [1 0 1 0 0]
第二行 [2 0 2 1 1]
第三行 [3 1 3 2 2]
第四行 [4 0 0 3 0]

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
class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """

        if len(matrix) == 0:
            return 0

        heights = [0] * len(matrix[0])
        res = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0
            res = max(res, self.largestRectangleArea(heights))
        return res

    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """

        if len(heights) == 0:
            return 0
        res = 0
        stack = []
        for i in range(len(heights)):
            while stack and heights[i] < heights[stack[-1]]:
                index = stack.pop()
                left = stack[-1] if stack else -1
                res = max(res, (i - left - 1) * heights[index])
            stack.append(i)

        while stack:
            index = stack.pop()
            left = stack[-1] if stack else -1
            res = max(res, (len(heights) - left - 1) * heights[index])

        return res

150. 逆波兰表达式求值

题目描述

根据逆波兰表示法，求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

  • 整数除法只保留整数部分。
  • 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

1
2
3
输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9

示例 2：

1
2
3
输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: (4 + (13 / 5)) = 6

示例 3：

1
2
3
4
5
6
7
8
9
10
输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
输出: 22
解释: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

解题思路

在python中，(-1)/2=-1，而在c语言中，(-1)/2=0。也就是c语言中，除法是向零取整，即舍弃小数点后的数。而在python中，是向下取整的。而这道题的oj是默认的c语言中的语法，所以需要在遇到’/’的时候注意一下。

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 evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        stack = []
        for c in tokens:
            if c not in ('+','-','*','/'):
                stack.append(c)
            else:
                a = int(stack.pop())
                b = int(stack.pop())
                if c == '+':
                    stack.append(str(b+a))
                if c == '-':
                    stack.append(str(b-a))
                if c == '*':
                    stack.append(str(b*a))
                if c == '/':
                    if b*a < 0 and b%a != 0:
                        stack.append(str(b/a+1))
                    else:
                        stack.append(str(b/a))
        return int(stack[0])

155. 最小栈

题目描述

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

  • push(x) — 将元素 x 推入栈中。
  • pop() — 删除栈顶的元素。
  • top() — 获取栈顶元素。
  • getMin() — 检索栈中的最小元素。

示例:

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

解题思路

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
class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.data = []
        self.min = []

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        self.data.append(x)
        if not self.min or x <= self.min[-1]:
            self.min.append(x)

    def pop(self):
        """
        :rtype: void
        """
        val = self.data.pop()
        if val == self.min[-1]:
            self.min.pop()

    def top(self):
        """
        :rtype: int
        """
        return self.data[-1]
        

    def getMin(self):
        """
        :rtype: int
        """
        return self.min[-1]
        


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

224. 基本计算器

题目描述

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。

示例 1:

1
2
输入: "1 + 1"
输出: 2

示例 2:

1
2
输入: " 2-1 + 2 "
输出: 3

示例 3:

1
2
输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23

说明：

你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。

解题思路

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
51
52
class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """

        if len(s) == 0:
            return 0
        if len(s) == 1:
            return int(s[0])

        stack = []
        i = 0
        while i < len(s):
            if s[i] == ')':
                helpStack = []
                while stack and stack[-1] != '(':
                    helpStack.insert(0, stack.pop())
                stack.pop()
                stack.append(self.help(helpStack))
            elif s[i] in "+-(":
                stack.append(s[i])
            elif s[i] in "0123456789":
                num = 0
                while i < len(s) and s[i] not in ['+', '-', '(', ')', ' ']:
                    num = num * 10 + int(s[i])
                    i += 1
                i -= 1
                stack.append(num)
            i += 1

        if len(stack) != 1:
            stack.append(self.help(stack))

        return stack[0]

    def compute(self, b, op, a):
        if op == '+':
            return b + a
        elif op == '-':
            return b - a

    def help(self, stack):
        if len(stack) == 1:
            return int(stack[0])
        while len(stack) >= 3:
            a = int(stack.pop(0))
            op = stack.pop(0)
            b = int(stack.pop(0))
            stack.insert(0, self.compute(a, op, b))
        return stack[0]

225. 用队列实现栈

题目描述

使用队列实现栈的下列操作：

1
2
3
4
push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空

注意:

你只能使用队列的基本操作— 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

解题思路

使用一个队列，每次新元素进队列的时候，先把当前的数字进入队列，然后把它前面的所有的元素移到新进队的后面。

例如：
1进队列， [1] -> [1]
2进队列, [1,2] ->[2,1]
3进队列, [2,1,3] ->[3,2,1]
4进队列, [3,2,1,4] ->[4,3,2,1]

栈顶为第一个元素

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 = collections.deque()
        

    def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: None
        """
        self.queue.append(x)
        for i in range(len(self.queue)-1):
            self.queue.append(self.queue.popleft())
        

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

    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. 用栈实现队列

题目描述

使用栈实现队列的下列操作：

push(x) — 将一个元素放入队列的尾部。
pop() — 从队列首部移除元素。
peek() — 返回队列首部的元素。
empty() — 返回队列是否为空。
示例:

1
2
3
4
5
6
7
MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:

你只能使用标准的栈操作 — 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

解题思路

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
51
52
53
54
55
class MyQueue(object):

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

    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: None
        """
        self.stack1.append(x)
        

    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()
        

    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2[-1]
        

    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        return not self.stack1 and not self.stack2
        


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
Donate comment here
------------The End------------
0%