抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

LeetCode-Hot100-栈

leetcode

发布于：2024年11月18日

字数：2.7k 字

时长：12 分钟

前言

题单LeetCode 热题 100的栈部分，给出解析。

20. Valid Parentheses

原题链接

题目描述

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Example 1: 

1
2
Input: s = "()"
Output: true

Example 2: 

1
2
Input: s = "()[]{}"
Output: true

Example 3: 

1
2
Input: s = "(]"
Output: false

Constraints:

  • 1 <= s.length <= 10^4
  • s consists of parentheses only '()[]{}'.

解题方法

要判断一个字符串 s 是否是有效的括号组合，可以使用栈（Stack）这一数据结构来处理。

解决方法步骤：

  1. 遍历字符串
  2. 使用栈来储存左括号：每当遇到一个左括号 (, {, [, 就将它压入栈中。
  3. 匹配右括号：每当遇到一个右括号 ), }, ]，从栈中弹出栈顶元素并检查是否与当前右括号匹配。如果匹配，则继续。如果不匹配，或者栈为空，则说明字符串无效。
  4. 检查栈是否为空：遍历完字符串后，如果栈为空，说明所有的括号都匹配成功，字符串是有效的；否则，字符串无效。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isValid(self, s: str) -> bool:
        # 用来匹配的字典，右括号为键，左括号为值
        matching_dict = {')': '(', '}': '{', ']': '['}
        stack = []

        for char in s:
            if char in matching_dict:  # 如果是右括号
                # 栈弹出的值和匹配的值进行比较，三元运算符确保栈为空时仍能够执行代码
                top_element = stack.pop() if stack else '#'
                if matching_dict[char] != top_element:
                    return False
            else:
                # 如果是左括号，压入栈中
                stack.append(char)

        # 如果栈为空，说明所有括号都匹配
        return not stack

复杂度分析

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

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

155. Min Stack

原题链接

题目描述

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

  • MinStack() initializes the stack object.
  • void push(int val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Example 1: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints:

  • -2^31 <= val <= 2^31 - 1
  • Methods pop, top and getMin operations will always be called on non-empty stacks.
  • At most 3 * 10^4 calls will be made to push, pop, top, and getMin.

解题方法

使用一个辅助栈 min，用于存取 stack 中最小值。

代码实现

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
class MinStack:

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

    # 每当push()新值进来时，如果 小于等于 min_stack 栈顶值，则一起 push() 到 min_stack，即更新了栈顶最小值；

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min or x <= self.min[-1]:
            self.min.append(x)

    # 判断将 pop() 出去的元素值是否是 min_stack 栈顶元素值（即最小值），
    # 如果是则将 min_stack 栈顶元素一起 pop()，这样可以保证 min_stack 栈顶元素始终是 stack 中的最小值。
    def pop(self) -> None:
        if self.stack.pop() == self.min[-1]:
            self.min.pop()

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

    def getMin(self) -> int:

        return self.min[-1]

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

复杂度分析

时间复杂度：$O(1)$ ：压栈，出栈，获取最小值的时间复杂度都为 O(1)。
空间复杂度：$O(n)$ ：包含 n 个元素辅助栈占用线性大小的额外空间。

394. Decode String

原题链接

题目描述

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 10^5.

Example 1: 

1
2
Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2: 

1
2
Input: s = "3[a2[c]]"
Output: "accaccacc"

Example 3: 

1
2
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Constraints:

  • 1 <= s.length <= 30
  • s consists of lowercase English letters, digits, and square brackets '[]'.
  • s is guaranteed to be a valid input.
  • All the integers in s are in the range [1, 300].

解题方法

要解码一个按照指定规则编码的字符串，可以使用栈结构来处理。具体步骤如下：

  1. 初始化栈：创建一个栈用于存放字符和数字。

  2. 遍历字符串：依次处理字符串中的每个字符。

    • 如果是数字，则构建完整的重复次数 k（可能由多位数字组成）。
    • 如果是左方括号 [，将当前构建的数字 k 压入栈，并开始一个新的编码上下文。
    • 如果是右方括号 ]，则从栈中弹出最近的字符串和重复次数，进行解码并将结果放回栈中。
    • 如果是字母，则直接将其添加到当前的解码字符串中。

  3. 构建最终结果：遍历结束后，栈中将只剩下一个解码后的字符串，作为最终结果返回。

代码实现

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
class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        current_num = 0
        current_str = ""
        
        for char in s:
            if char.isdigit():
                current_num = current_num * 10 + int(char)  # 处理多位数字
            elif char == '[':
                # 将当前字符串和数字入栈
                stack.append(current_str)
                stack.append(current_num)
                # 重置当前字符串和数字
                current_str = ""
                current_num = 0
            elif char == ']':
                # 弹出数字和字符串，进行解码
                num = stack.pop()
                prev_str = stack.pop()
                current_str = prev_str + current_str * num  # 重复并拼接
            else:
                # 普通字符，直接添加到当前字符串
                current_str += char
        
        return current_str

复杂度分析

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

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

739. Daily Temperatures

原题链接

题目描述

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i^th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1: 

1
2
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2: 

1
2
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3: 

1
2
Input: temperatures = [30,60,90]
Output: [1,1,0]

Constraints:

  • 1 <= temperatures.length <= 10^5
  • 30 <= temperatures[i] <= 100

解题方法

题目的意思实际上就是给定一个数组，每个位置上有整数值。对于每个位置，在该位置右侧找到第一个比当前元素更大的元素。求「该元素」与「右侧第一个比当前元素更大的元素」之间的距离，将所有距离保存为数组返回结果。

最简单的思路是对于每个温度值，向后依次进行搜索，找到比当前温度更高的值。

更好的方式使用「单调递增栈」，栈中保存元素的下标。

解题思路：

  1. 将答案数组 ans 全部赋值为 0，然后遍历数组每个位置元素。
  2. 如果栈为空，则将当前元素的下标入栈。
  3. 如果栈不为空，且当前数字大于栈顶元素对应的数字，栈顶元素出栈，计算下标差。
  4. 此时当前元素就是栈顶元素的下一个更高值，将其下标差存入 ans 数组中保存起来，判断栈顶元素。
  5. 直到当前数字小于或等于栈顶元素，则停止出栈，将当前元素下标入栈。
  6. 输出数组 ans。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        # 初始化答案数组
        ans = [0] * n
        # 单调递增栈
        st = []
        # 遍历
        for i, temp in enumerate(temperatures):
            # 当前温度大于栈顶，出栈，计算下标差存入答案数组
            while st and temperatures[st[-1]] < temp:
                idx = st.pop()
                ans[idx] = i - idx
            # 当前温度小于栈顶元素，入栈
            st.append(i)
        return ans

复杂度分析

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

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

84. Largest Rectangle in Histogram

题目链接

题目描述

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1: 

1
2
3
4
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2: 

1
2
Input: heights = [2,4]
Output: 4

Constraints:

  • 1 <= heights.length <= 10^5
  • 0 <= heights[i] <= 10^4

解题方法

这个问题是经典的「最大矩形面积」问题，可以通过使用栈来有效地解决。

思路：

  1. 栈的应用：

    • 我们遍历整个高度数组 heights，并使用栈来存储柱子的索引。栈中保持的是按高度递增的顺序。
    • 如果当前柱子的高度大于栈顶的柱子高度，说明可以继续加入栈中；如果当前柱子的高度小于栈顶的柱子高度，说明之前的柱子可以计算出矩形的面积了。

  2. 如何计算面积：

    • 当遇到一个比栈顶柱子低的柱子时，我们可以出栈，计算出以栈顶柱子为最矮柱子的矩形的面积。矩形的宽度是由当前柱子的索引与栈顶柱子的前一个索引决定的。

  3. 最后处理栈中的剩余柱子：

    • 如果栈中还有剩余的柱子，说明这些柱子的高度一直延伸到了数组的末尾，我们需要再一次进行面积计算。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # 初始化一个栈，栈中存放的是柱子的索引
        stack = []
        max_area = 0
        # 在 heights 数组的末尾加入一个 0 来确保最后能清空栈
        heights.append(0)
        
        for i in range(len(heights)):
            # 如果当前柱子的高度小于栈顶柱子的高度，计算面积
            while stack and heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]  # 取出栈顶柱子的高度
                # 宽度是当前索引 i 和栈顶索引的下一个索引之间的差
                w = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, h * w)  # 更新最大面积
            stack.append(i)  # 将当前柱子索引加入栈中
        
        return max_area

复杂度分析

时间复杂度：每个元素最多被推入栈一次，也最多被弹出一次，因此时间复杂度是 $O(n)$，其中 $n$ 是柱子的数量。

空间复杂度：由于使用了栈来存储柱子的索引，空间复杂度为 $O(n)$。

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://blog.skyheart.moe/posts/f52970dc/

更新于：2024年11月18日

栈

评论