力扣热题 100：栈专题经典题解析

系列文章目录

力扣热题 100：哈希专题三道题详细解析(JAVA)
力扣热题 100：双指针专题四道题详细解析(JAVA)
力扣热题 100：滑动窗口专题两道题详细解析（JAVA）
力扣热题 100：子串专题三道题详细解析(JAVA)
力扣热题 100：普通数组专题五道题详细解析(JAVA)
力扣热题 100：矩阵专题四道题详细解析（JAVA）
力扣热题 100：链表专题经典题解析(前7道)
力扣热题 100：链表专题经典题解析（后7道）
力扣热题 100：二叉树专题经典题解析（前8道）
力扣热题 100：二叉树专题进阶题解析（后7道）
力扣热题 100：图论专题经典题解析
力扣热题 100：回溯专题经典题解析
力扣热题 100：二分查找专题经典题解析
力扣热题 100：栈专题经典题解析
力扣热题 100：堆专题经典题解析
力扣热题 100：贪心算法专题经典题解析
力扣热题 100：动态规划专题经典题解析
力扣热题 100：多维动态规划专题经典题解析
力扣热题 100：技巧专题经典题解析

在力扣（LeetCode）平台上，栈相关的题目是算法面试和练习中的重要部分。今天，我们就来详细解析栈专题中的几道经典题目，帮助大家更好地理解解题思路和技巧。

一、有效的括号（题目 20）

1. 题目描述

给定一个只包含三种括号 '()'、'[]' 和 '{}' 的字符串，判断该字符串是否有效。有效字符串需满足：

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

2. 示例

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "([)]"

输出：false

3. 解题思路

这道题主要考察栈的应用。我们可以使用栈来匹配括号，具体步骤如下：

1. 初始化一个栈，用于存储左括号。
2. 遍历字符串中的每个字符：
   • 如果是左括号，将其压入栈中。
   • 如果是右括号，检查栈是否为空以及栈顶元素是否为对应的左括号。如果是，则弹出栈顶元素；否则，返回 false。
3. 遍历结束后，栈为空则说明所有括号都匹配，返回 true；否则，返回 false。

4. 代码实现（Java）

import java.util.Stack;

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是字符串的长度。每个字符最多被压入和弹出栈一次。
• 空间复杂度 ：O(n)，栈的大小在最坏情况下为 n/2。

二、最小栈（题目 155）

1. 题目描述

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

2. 示例

示例 1：

输入：

["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：

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

3. 解题思路

这道题主要考察栈的设计。我们可以使用两个栈，一个用于存储所有元素，另一个用于存储最小值。具体步骤如下：

1. 初始化两个栈 stack 和 minStack。
2. push 操作：将元素压入 stack，同时如果 minStack 为空或元素小于等于 minStack 栈顶元素，则将元素压入 minStack。
3. pop 操作：弹出 stack 栈顶元素，如果该元素等于 minStack 栈顶元素，则同时弹出 minStack 栈顶元素。
4. top 操作：返回 stack 栈顶元素。
5. getMin 操作：返回 minStack 栈顶元素。

4. 代码实现（Java）

import java.util.Stack;

public class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
    }

    public void pop() {
        if (!stack.isEmpty()) {
            int top = stack.pop();
            if (top == minStack.peek()) {
                minStack.pop();
            }
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

5. 复杂度分析

• 时间复杂度 ：所有操作的时间复杂度均为 O(1)。
• 空间复杂度 ：O(n)，其中 n 是栈中元素的数量。

三、字符串解码（题目 394）

1. 题目描述

给定一个经过编码的字符串，返回其解码后的字符串。编码规则为 k[encoded_string]，表示 encoded_string 被重复 k 次。

2. 示例

示例 1：

输入：s = "3[a]2[bc]"

输出："aaabcbc"

3. 解题思路

这道题主要考察栈的应用。我们可以使用两个栈，一个用于存储字符，另一个用于存储数字。具体步骤如下：

1. 初始化两个栈 charStack 和 numStack。
2. 遍历字符串中的每个字符：
   • 如果是数字，计算完整的数字并压入 numStack。
   • 如果是 ‘[’，压入 charStack。
   • 如果是 ‘]’，弹出 charStack 中的字符直到遇到 ‘[’，形成一个子字符串，然后根据 numStack 中的数字重复该子字符串，并将其压回 charStack。
   • 如果是字母，压入 charStack。
3. 最后，将 charStack 中的字符拼接成字符串。

4. 代码实现（Java）

import java.util.Stack;

public class Solution {
    public String decodeString(String s) {
        Stack<Integer> numStack = new Stack<>();
        Stack<Character> charStack = new Stack<>();
        int num = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '[') {
                numStack.push(num);
                num = 0;
                charStack.push(c);
            } else if (c == ']') {
                StringBuilder sb = new StringBuilder();
                while (charStack.peek() != '[') {
                    sb.append(charStack.pop());
                }
                charStack.pop();
                int repeat = numStack.pop();
                String repeated = sb.toString().repeat(repeat);
                for (char ch : repeated.toCharArray()) {
                    charStack.push(ch);
                }
            } else {
                charStack.push(c);
            }
        }
        StringBuilder result = new StringBuilder();
        while (!charStack.isEmpty()) {
            result.append(charStack.pop());
        }
        return result.reverse().toString();
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是字符串的长度。每个字符最多被压入和弹出栈一次。
• 空间复杂度 ：O(n)，栈的大小在最坏情况下为 n。

四、每日温度（题目 739）

1. 题目描述

给定一个整数数组 temperatures，表示每天的温度。请计算一个数组 answer，其中 answer[i] 是指下一次温度更高的那个日子的索引与当前日子的索引之差。如果之后都没有更高的温度，则 answer[i] = 0。

2. 示例

示例 1：

输入：temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

输出：[1, 1, 4, 2, 1, 1, 0, 0]

3. 解题思路

这道题主要考察栈的应用。我们可以使用单调栈来解决这个问题。具体步骤如下：

1. 初始化一个栈，用于存储温度的索引。
2. 遍历温度数组，对于每个温度：
   • 如果栈不为空且当前温度大于栈顶索引对应的温度，则弹出栈顶索引，并计算天数差，存入结果数组。
   • 将当前索引入栈。
3. 遍历结束后，栈中剩余的索引对应的结果为 0。

4. 代码实现（Java）

import java.util.Stack;

public class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int index = stack.pop();
                answer[index] = i - index;
            }
            stack.push(i);
        }
        return answer;
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是温度数组的长度。每个索引最多被压入和弹出栈一次。
• 空间复杂度 ：O(n)，栈的大小在最坏情况下为 n。

五、柱状图中最大的矩形（题目 84）

1. 题目描述

给定一个非负整数数组 heights，表示一组柱状图的高度，计算能够形成的矩形的最大面积。

2. 示例

示例 1：

输入：heights = [2, 1, 5, 6, 2, 3]

输出：10

解释：最大面积的矩形由高度为 5 的柱子和其右侧的柱子形成，宽度为 2，面积为 5 * 2 = 10。

3. 解题思路

这道题主要考察栈的应用。我们可以使用单调栈来解决这个问题。具体步骤如下：

1. 初始化一个栈，用于存储柱子的索引。
2. 遍历柱状图，对于每个柱子：
   • 如果栈不为空且当前柱子的高度小于栈顶柱子的高度，则弹出栈顶柱子，并计算以该柱子为高度的最大矩形面积。
   • 将当前柱子的索引入栈。
3. 遍历结束后，处理栈中剩余的柱子。

4. 代码实现（Java）

import java.util.Stack;

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i <= heights.length; i++) {
            int currentHeight = (i == heights.length) ? 0 : heights[i];
            while (!stack.isEmpty() && currentHeight < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是柱状图的高度数组的长度。每个索引最多被压入和弹出栈一次。
• 空间复杂度 ：O(n)，栈的大小在最坏情况下为 n。

以上就是力扣热题 100 中与栈相关的经典题目的详细解析，希望对大家有所帮助。在实际刷题过程中，建议大家多动手实践，理解解题思路的本质，这样才能更好地应对各种算法问题。