leetcode（栈）

发表于 | 分类于 | 页面访问量 次
字数统计: 979 字 | 阅读时长 ≈ 4 分钟

菜 682(E)

中 71(C-) 、394(C+)

危 42(B+) 、84(A)

栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

小练总结：栈的题相对来说比较简单，需要注意的问题就是模型转化跟栈结合时需要细心一些。实际问题转化为算法时，逻辑上的判断至关重要。

682. 棒球比赛（E）

分析：栈初试身手。选了一道简单难度的题。嗯，果然很简单。读清题意，解答很容易的。栈最后位，表示就是用队列的[-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def calPoints(self, ops: List[str]) -> int:
        points = []
        i = 0
        while i < len(ops):
            if ops[i] == 'C':
                points.pop()
            elif ops[i] == '+':
                points.append(points[-1] + points[-2])
            elif ops[i] == 'D':
                points.append(points[-1] * 2)
            else:
                points.append(int(ops[i]))
            i += 1
        return sum(points)

71. 简化路径（C-）

分析：本质上还是一道简单的栈表示。题意理解上稍微复杂一点。如果不熟悉Linux路径表示，需要细心看一下。..删除的是前面出现的路径。整体思路就是分段，去空，判断，构建栈。最后别忘了拼接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def simplifyPath(self, path: str) -> str:
        l = path.split('/')
        l = [i for i in l if i]
        stack = []
        
        while l:
            c = l.pop(0)
            if c == '.':
                continue
            elif c == '..':
                if stack:
                    stack.pop(-1)
            else:
                stack.append(c)

        return '/'+'/'.join(stack)

394. 字符串解码（C+）

分析：题意容易理解。关键点在于，数字和字母构建双重栈。如果没有数字添加默认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
class Solution:
    def decodeString(self, s: str) -> str:
        result = ''
        stack = []#模拟栈
        for i in s:
            if i != ']':
                stack.append(i)
            else:
                temp1 = []#存字母
                while stack[-1] != "[":
                    temp1.append(stack.pop())
                temp1_list = list(temp1)
                stack.pop()#去除[
                    
                temp2 = []#存数字
                if len(stack)!=0:
                    while stack[-1] in "0123456789":  #做循环是为了防止高位数出现
                        temp2.append(stack.pop())
                        if len(stack)==0:
                            break
                if temp2 == []:
                    temp2= ['1']
                stack.append(eval("".join(temp2[::-1]))*"".join(temp1[::-1]))#先反转列表形成字符串，然后相乘，添加到stack
                
        for i in stack:
            result += i
        return result

遇事不决用正则。正则用好了，超级容易实现，然鹅！这道题考察栈。

1
2
3
4
5
class Solution(object):
    def decodeString(self, s):
        while '[' in s:
            s = re.sub(r"(\d+)\[(\w+)\]",lambda m:int(m.group(1))*m.group(2),s)
        return s

42. 接雨水（B+）

分析：hard难度，就有点意思了。感觉更多的是，找到规律。两边分别遍历一下，墙和水被加了两次，再减去墙。最后减去整体面积。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        h1 = 0
        h2 = 0
        for i in range(len(height)):
            h1 = max(h1,height[i])
            h2 = max(h2,height[-i-1])
            ans = ans + h1 + h2 -height[i]
        return  ans - len(height)*h1

84. 柱状图中最大的矩形（A）

分析：感觉许久未逢的几何生疏感，想了一阵才缕清算法思路，虽然对步骤还有点违和感。

算法书写不难，不过这个思路的构建还是需要学习一下的。关键点在于，右侧高于左侧，放入栈中。低于左侧，就开始计算面积。判断，左右边界，求面积。是i中的高，还是栈中的高，直接影响面积。最后加个0是收尾计算。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(0)   #控制边界做最后收尾验算
        stack = [-1]
        res = 0
        for i in range(len(heights)):
            while stack and heights[stack[-1]]>heights[i]:  #如果栈中圆柱高于新圆柱
                s = stack.pop()  #i<i-1.右边界为i-1出栈。
                res = max(res,(i-stack[-1]-1)*heights[s])
            stack.append(i)
        return res
0%
undefined