算法刷题笔记03：Stack、Queue

Hsinyan

发布于 2022-08-30 15:21:15

2410

发布于 2022-08-30 15:21:15

文章被收录于专栏：Hsinyan写字的地方Hsinyan写字的地方

Stack、Queue

20.有效的括号

题目描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

题目链接：https://leetcode-cn.com/problems/valid-parentheses/

解法 1：暴力

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        while "{}" in s or '[]' in s or '()' in s:
            s = s.replace('{}','').replace('[]','').replace('()','')
        
        return s ==''

使用replace函数，需要注意一下 while 循环终止条件。

解法 2：使用辅助栈

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        for i in s:
            if i =='{':
                stack.append('}')
            elif i == '(':
                stack.append(')')
            elif i == '[':
                stack.append(']')
            elif len(stack) != 0 and i == stack[-1]:
                stack.pop()
            else:
                return False
        
        return len(stack)==0

155.最小栈

题目描述

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

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

题目链接：https://leetcode-cn.com/problems/min-stack/

解法

class MinStack(object):

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


    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)


    def pop(self):
        """
        :rtype: None
        """
        if self.stack:
            x = self.stack.pop()
            if x == self.min_stack[-1]:
                self.min_stack.pop()

    def top(self):
        """
        :rtype: int
        """
        if not self.stack: return -1
        return self.stack[-1]


    def getMin(self):
        """
        :rtype: int
        """
        if self.min_stack:
            return self.min_stack[-1]
        return 0

   
# 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()

题目要求在常数时间内获得栈中的最小值，因此不能在 getMin() 的时候再去计算最小值，所以可以维护两个栈，用来存放最小值，这也是一种常见的做法。

84.柱状图中最大的矩形

题目描述

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

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

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

题目链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram

解法 1：暴力求解

class Solution(object):
        def largestRectangleArea(self, heights):
            """
            :type heights: List[int]
            :rtype: int
            """
            res = 0
            for i in range(len(heights)):
                # 当前高度
                cur_height = heights[i]

                # 取当前高度时的左边界
                left = i
                while left > 0 and heights[left-1]>=cur_height:
                    left-=1
                # 取当前高度时的右边界
                right = i 
                while right<len(heights)-1 and heights[right+1]>=cur_height:
                    right+=1
                #更新最大值
                res = max(cur_height*(right-left+1),res)

            return res

这种可以求解，时间复杂度为O(n^2)，实际提交的时候超时了。

解法 2：辅助栈

class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        res = 0
        # 加入哨兵结点
        heights = [0] + heights + [0]
        stack = [0]

        # 第一个是哨兵结点，所以从1开始遍历
        for i in range(1,len(heights)):
            # 当高度小于栈顶时，说明找到了右边界
            while heights[i] < heights[stack[-1]]:
                cur_height = heights[stack.pop()]
                cur_width = i-stack[-1] -1
                res = max(cur_height*cur_width,res)
            stack.append(i)
        return res

这里参考了 LeetCode 的题解：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/