Leetcode题解-算法-栈和队列(python版)

喜欢ヅ旅行 2022-10-16 07:24 175阅读 0赞

### 文章目录 ###

*   *  1、用栈实现队列
     *  2、用队列实现栈
     *  3、最小值栈
     *  4、括号匹配
     *  5、数组中下一个比大自己的元素和自己的距离
     *  6、循环数组中比当前元素大的下一个元素
     *  7、字符串解码
     *  8、接雨水

## 1、用栈实现队列 ##

[232. 用栈实现队列(Easy)][232. _Easy]

class MyQueue(object):
    
        def __init__(self):
            self.stack_1 = []
            self.stack_2 = []
    
        def push(self, x):
            self.stack_1.append(x)
    
        def pop(self):
            if not self.stack_2:
                while self.stack_1:
                    self.stack_2.append(self.stack_1.pop())
            return self.stack_2.pop()
    
        def peek(self):
            if not self.stack_2:
                while self.stack_1:
                    self.stack_2.append(self.stack_1.pop())
            return self.stack_2[-1] if self.stack_2 else None
    
        def empty(self):
            return not self.stack_1 and not self.stack_2

## 2、用队列实现栈 ##

[225. 用队列实现栈(Easy)][225. _Easy]

class MyStack(object):
    
        def __init__(self):
            self.queue1 = collections.deque()
            self.queue2 = collections.deque()
    
        def push(self, x):
            self.queue2.append(x)
            while self.queue1:
                self.queue2.append(self.queue1.popleft())
            self.queue1, self.queue2 = self.queue2, self.queue1
    
        def pop(self):
            return self.queue1.popleft()
    
        def top(self):
            return self.queue1[0]
    
        def empty(self):
            return not self.queue1

时间复杂度：入栈操作 O(n)，其余操作 O(1)

## 3、最小值栈 ##

[155. 最小栈(Easy)][155. _Easy]

class MinStack(object):
    
        def __init__(self):
            self.stack1 = []
            self.stack_min = []
    
        def push(self, val):
            self.stack1.append(val)
            if not self.stack_min or val <= self.stack_min[-1]:
                self.stack_min.append(val)
    
        def pop(self):
            if self.stack1[-1] == self.stack_min[-1]:
                self.stack_min.pop()
            return self.stack1.pop()
    
        def top(self):
            return self.stack1[-1]
    
        def getMin(self):
            return self.stack_min[-1]

## 4、括号匹配 ##

[20. 有效的括号(Easy)][20. _Easy]

每碰见 ‘(’, ‘\{’, ‘\[’ 就将其压入栈中，每碰见 ‘)’, ‘\}’, '\]'就查看栈如果为空或栈顶元素不匹配返回 false，如果匹配弹出栈顶元素，直到匹配完所有字符，如果栈为空返回 true。

class Solution(object):
        def isValid(self, s):
            stack = []
            left = ['(', '[', '{']
            for c in s:
                if c in left:
                    stack.append(c)
                elif c == ")":
                    if not stack or stack[-1] != '(':
                        return False
                    stack.pop()
                elif c == "]":
                    if not stack or stack[-1] != '[':
                        return False
                    stack.pop()
                elif c == '}':
                    if not stack or stack[-1] != "{":
                        return False
                    stack.pop()
            return not stack
                
            """
            :type s: str
            :rtype: bool
            """

## 5、数组中下一个比大自己的元素和自己的距离 ##

[739. 每日温度(Medium)][739. _Medium]

方法：单调栈

用栈来保存元素的下标，遍历数组，如果当前元素大于栈顶元素作为下标对应的数值，弹出，也找到了栈顶元素作为下标对应元素的下一个比自己大的元素距离。元素比当前元素大，将当前元素下标入栈。

class Solution(object):
        def dailyTemperatures(self, temperatures):
            n = len(temperatures)
            res = [0] * n
            stack = []
            for i in range(n):
                while stack and temperatures[stack[-1]] < temperatures[i]:
                    pre_index = stack.pop()
                    res[pre_index] = i - pre_index
                stack.append(i)
            return res

## 6、循环数组中比当前元素大的下一个元素 ##

[503. 下一个更大元素 II(Medium)][503. _ II_Medium]

用栈来保存元素的下标，从尾到头遍历数组，如果当前元素大于栈顶下标对应元素，弹出，直到找到比当前元素大的元素，或着栈为空，表示找不到（-1），从尾到头遍历两次，即得出结论。

class Solution(object):
        def nextGreaterElements(self, nums):
            n = len(nums)
            stack = [0] * n
            res = [-1] * n
            for i in range(2 * n):
                while stack and nums[i % n] > nums[stack[-1]]:
                    res[stack.pop()] = nums[i % n]
                stack.append(i % n)
            return res

时间复杂度: O(n)  
空间复杂度: O(n)

## 7、字符串解码 ##

[394. 字符串解码(Medium)][394. _Medium]

本题中可能出现括号嵌套的情况，比如 2\[a2\[bc\]\]，这种情况下我们可以先转化成 2\[abcbc\]，在转化成 abcbcabcbc。具体的做法是，遍历这个栈：

*  如果不是右括号，直接入栈；
 *  遇到右括号，取出栈中括号内的元素bc，再取出重复次数 2，拼接为 bcbc，再次入栈，栈中元素由 2\[a2\[bc 变为 2\[abcbc
 *  再次遇到右括号，重复上面操作，栈中元素由 2\[abcbc 变为 abcbcabcbc

class Solution(object):
        def decodeString(self, s):
            stack = []
            for c in s:
                if c == "]":
                    tmp_str = ""
                    while stack[-1] != '[':
                        tmp_str = stack.pop() + tmp_str
                    stack.pop()
                    count = ""
                    while stack and stack[-1] >= '0' and stack[-1] <= '9':
                        count = stack.pop() + count
                    tmp_str = tmp_str * int(count)
                    for cc in tmp_str:
                        stack.append(cc)
                else:
                    stack.append(c)
            return ''.join(stack)

## 8、接雨水 ##

[42. 接雨水(Hard)][42. _Hard]

**方法 1：动态编程**

对于当前柱子可以装多少水取决于他左边最高的柱子和右边最高的柱子，如下图所示，当前柱子左侧最高的柱子高度为 2，右侧最高柱子高度为 3，能接多少水取决于左边的柱子，等于左右最高柱子的最小高度减去当前柱子高度。

算法：

*  找到数组中从下标 i 到最左端最高的条形块高度 max\_left。
 *  找到数组中从下标 i 到最右端最高的条形块高度 max\_right。
 *  扫描数组 height 并更新答案：
    
     *  累加 min(max\_left\[i\], max\_right\[i\]) - height\[i\] 到 res 上

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhcHB5amFjb2I_size_16_color_FFFFFF_t_70]

class Solution:
        def trap(self, height: List[int]) -> int:
            n = len(height)
            res = 0
            if n == 0:
                return res
            max_left = [0]*n
            max_right = [0]*n
            max_left[0] = height[0]
            max_right[n-1] = height[n-1]
    
            for i in range(1, n-1):
                if height[i] > max_left[i-1]:
                    max_left[i] = height[i]
                else:
                    max_left[i] = max_left[i-1]
    
            for i in range(n-2, -1, -1):
                if height[i] > max_right[i+1]:
                    max_right[i] = height[i]
                else:
                    max_right[i] = max_right[i+1]
            for i in range(1, n-1):
                res += min(max_left[i], max_right[i]) - height[i]
            return res

时间复杂度：O(n)  
空间复杂度：O(n)

**方法 2：栈的应用**  
上面的方法每次看当前柱子可以存储多少水，也可以每次看每个横条可以存储多少水，如图所示。  
![在这里插入图片描述][20200920095401614.png]  
在遍历数组时维护一个栈。如果当前的柱子小于或等于栈顶的柱子，我们将柱子的索引入栈。如果当前柱子高度大于栈顶柱子高度，则一定存在存储水的横条了，计算当前形成横条储存的水量，累加到 ans 。

结合下图说明一下：  
当前柱子高度为 1，比栈顶柱子高（栈顶柱子高度为 0），则一定有存储水的横条，将栈顶元素取出，取出后再拿栈顶横条高度（st\[-1\] 高度为 1）和当前横条高度相比较，min(height\[cur\], height\[st\[-1\]\]) - height\[top\] 就是当前可以存储水量的横条。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhcHB5amFjb2I_size_16_color_FFFFFF_t_70 1]  
算法：  
使用栈来存储柱子的索引下标。  
遍历数组

*  当栈非空且 height\[current\] > height\[st.top()\]
    
     *  意味着栈中元素可以被弹出。弹出栈顶元素 top。
     *  计算当前元素和栈顶元素的距离，准备进行填充操作  
        width = current − st.top() − 1
     *  找出界定高度  
        depth = min(height\[current\], height\[st.top()\]) − height\[top\]  
        往答案中累加积水量 ans += width × depth
 *  将当前索引下标入栈
 *  将 current 移动到下个位置

class Solution:
        def trap(self, height: List[int]) -> int:
            res = 0
            st = []
            current = 0
            while current < len(height):
                while st and height[current] > height[st[-1]]:
                    top = st[-1]
                    st.pop()
                    if not st:
                        break
                    width = current - st[-1] - 1
                    depth = min(height[current], height[st[-1]]) - height[top]
                    res += width * depth
                st.append(current)
                current += 1
            return res

[232. _Easy]: https://leetcode-cn.com/problems/implement-queue-using-stacks/
[225. _Easy]: https://leetcode-cn.com/problems/implement-stack-using-queues/
[155. _Easy]: https://leetcode-cn.com/problems/min-stack/
[20. _Easy]: https://leetcode-cn.com/problems/valid-parentheses/submissions/
[739. _Medium]: https://leetcode-cn.com/problems/daily-temperatures/
[503. _ II_Medium]: https://leetcode-cn.com/problems/next-greater-element-ii/
[394. _Medium]: https://leetcode-cn.com/problems/decode-string/
[42. _Hard]: https://leetcode-cn.com/problems/trapping-rain-water/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhcHB5amFjb2I_size_16_color_FFFFFF_t_70]: /images/20221014/f9f788b9f9cf4f879b2617ae2a290071.png
[20200920095401614.png]: /images/20221014/bf48dd4f3d8549359e1c970cba566780.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhcHB5amFjb2I_size_16_color_FFFFFF_t_70 1]: /images/20221014/03dd708f90ca432e915a866851049dd3.png