算法长征（6）栈

发表于 更新于 分类于 ， 阅读次数： 本文字数： 3.2k 阅读时长 ≈ 6 分钟

栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

  • self.smin = [] 存储最小栈元素，记录当前最小值是什么。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class MinStack:
    def __init__(self):
        self.sdata = []
        self.smin = []
        
    def push(self, x: int) -> None:
        self.sdata.append(x)
        if not self.smin or self.smin[-1] >= x:
            self.smin.append(x)

    def pop(self) -> None:
        if self.sdata.pop() == self.smin[-1]:
            self.smin.pop()

    def top(self) -> int:
        return self.sdata[-1]

    def min(self) -> int:
        return self.smin[-1]

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。注意 两个整数之间的除法只保留整数部分。

示例 1：

输入：tokens = ["2","1","+","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

  • 函数字典，isdigit只能判断正整数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        n = len(tokens)
        op = {
                '+': add,
                '-': sub,
                '*': mul,
                '/': lambda x, y: int(x / y)
        }
        stack = []
        for t in tokens:
            try:
                num = int(t)
            except ValueError:
                b = stack.pop()
                a = stack.pop()
                num = op[t](a, b)
            finally:
                stack.append(num)
        return stack[0]

单调栈

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

示例 1:

img 
1
2
3
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights = [0] + heights + [0] # 哨兵
        stack, res = [0], 0
        for i in range(1, len(heights)):
            while stack and heights[i] <= heights[stack[-1]]:
                tmp = stack.pop()
                if stack:
                    weith = i - stack[-1] - 1
                    if (t := heights[tmp] * weith) > res:
                        res = t
            stack.append(i)
        return res

给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。

注意：此题 matrix 输入格式为一维 01 字符串数组。

示例 1：

img 
1
2
3
输入：matrix = ["10100","10111","11111","10010"]
输出：6
解释：最大矩形如上图所示。
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
class Solution:
    def maximalRectangle(self, matrix: List[str]) -> int:
        def maximalhist(heights):
            heights = [0] + heights + [0]
            res, stack = 0, [0]
            for i in range(1, len(heights)):
                while stack and heights[i] <= heights[stack[-1]]:
                    tmp = stack.pop()
                    if stack:
                        weith = i - stack[-1] - 1
                        if (t := heights[tmp] * weith) > res:
                            res = t 
                stack.append(i)
            return res
        
        if not matrix:
            return 0
        m, n = len(matrix), len(matrix[0])
        pre = [0] * n
        ans = 0
        for i in range(m):
            for j in range(n):
                # if else 缩减
                if matrix[i][j] != '0':
                    pre[j] += int(matrix[i][j])
                else:
                    pre[j] = 0
            ans = max(ans, maximalhist(pre))
        return ans

给定一个整数数组 asteroids，表示在同一行的小行星。对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

示例 1：

输入：asteroids = [5,10,-5] 输出：[5,10] 解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        n = len(asteroids)
        stack = [0]
        for i in range(1, n):
            while stack and asteroids[stack[-1]] > 0 and asteroids[i] < 0:
                a = asteroids[stack[-1]]
                b = asteroids[i]
                if a + b < 0:
                    stack.pop()
                elif a + b > 0:
                    break
                elif a + b == 0:
                    stack.pop()
                    break
            else:
                stack.append(i)
        return [asteroids[i] for i in stack]

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        stack, ans = [0], [0] * n
        for i in range(1, n):
            while stack and temperatures[stack[-1]] < temperatures[i]:
                tmp = stack.pop()
                ans[tmp] = i - tmp
            stack.append(i)
        return ans