当前位置：首页 > news >正文

LeetCode 热题100 之栈

news 2024/11/7 20:15:19

1.有效的括号

在这里插入图片描述

思路分析：我们可以使用栈（stack）来解决这个问题。栈是一种先进后出的数据结构，这与括号匹配的需求非常契合。

unordered_map<char, char> bracket_map：这个哈希表用来存储右括号与左括号的对应关系。比如 ‘)’ 对应 ‘(’，‘}’ 对应 ‘{’，] 对应 [。
stack stk：我们使用栈来暂存左括号。当遇到右括号时，我们弹出栈顶元素，检查是否与当前右括号匹配。
遍历字符串：对于每个字符
- 如果是右括号，检查栈顶是否为与之匹配的左括号，如果不匹配，则返回false；
- 如果是左括号，直接入栈
栈的最终状态：如果栈为空，则说明所有的括号都匹配上了；如果栈为空，说明匹配失败，返回false

具体实现代码（详解版）：

class Solution {
public:bool isValid(string s) {// 创建一个哈希表，用于存储每个右括号对应的左括号unordered_map<char, char> bracket_map = {{')', '('},{'}', '{'},{']', '['}};stack<char> stk; // 栈用于存储左括号// 遍历字符串中的每个字符for (char c : s) {// 如果是右括号，检查栈顶是否匹配if (bracket_map.find(c) != bracket_map.end()) {// 如果栈为空，说明没有对应的左括号if (stk.empty() || stk.top() != bracket_map[c]) {return false;}stk.pop(); // 匹配成功，弹出栈顶元素} else {// 如果是左括号，压入栈stk.push(c);}}// 最终栈应为空，如果栈不为空，则说明有未匹配的左括号return stk.empty();}
};

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

2.最小栈

在这里插入图片描述
思路分析：要做出这道题目，首先要理解栈结构先进后出的性质。对于栈来说，如果一个元素 a 在入栈时，栈里有其它的元素 b, c, d，那么无论这个栈在之后经历了什么操作，只要 a 在栈中，b, c, d 就一定在栈中，因为在 a 被弹出之前，b, c, d 不会被弹出。
因此，在操作过程中的任意一个时刻，只要栈顶的元素是 a，那么我们就可以确定栈里面现在的元素一定是 a, b, c, d。那么，我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m。
按照上面的思路，我们只需要设计一个数据结构，使得每个元素 a 与其相应的最小值 m 时刻保持一一对应。因此我们可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。

当一个元素要入栈时，取当前辅助栈的栈顶存储的最小值，与当前元素比较得到最小值，将这个最小值插入辅助栈中；
当一个元素要出栈时，要把辅助栈的栈顶元素也一并弹出；
在任意一个时刻，栈内元素的最小值就是存储在辅助栈的栈顶元素中。

具体实现代码（详解版）：

class MinStack {stack<int> x_stack;      // 主栈，用于存储所有元素stack<int> min_stack;    // 辅助栈，用于存储每一步的最小值
public:// 构造函数，初始化 min_stack，将一个很大的值 (INT_MAX) 推入 min_stack 中，作为初始最小值。MinStack() {min_stack.push(INT_MAX); // 初始化时，辅助栈的栈顶是最大整数，表示最初没有最小值}// 将一个值压入栈void push(int val) {x_stack.push(val);  // 将值压入主栈// 将当前值和辅助栈栈顶的最小值进行比较，选择较小的一个压入辅助栈min_stack.push(min(min_stack.top(), val));  }// 弹出栈顶元素void pop() {x_stack.pop();  // 弹出主栈的栈顶元素min_stack.pop();  // 弹出辅助栈的栈顶元素，保持栈同步}// 获取栈顶元素int top() {return x_stack.top();  // 返回主栈的栈顶元素}// 获取当前栈中的最小值int getMin() {return min_stack.top();  // 返回辅助栈的栈顶元素，它存储当前栈中的最小值}
};/*** 用法示例：* MinStack* obj = new MinStack();  // 创建一个新的 MinStack 对象* obj->push(val);                  // 向栈中推入一个元素* obj->pop();                       // 弹出栈顶元素* int param_3 = obj->top();         // 获取栈顶元素* int param_4 = obj->getMin();      // 获取栈中的最小值*/

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

3.字符串解码

在这里插入图片描述
思路分析：这个问题是一个典型的栈问题，我们需要用栈来解决这个问题。解题的关键是通过遍历字符串并利用栈来处理嵌套的编码结构

遍历字符串
- 数字处理：遇到数字时，可能表示一个重复次数，需要将它组成一个完整的数字；
- ’['处理：将当前重复次数和当前字符串分别入对应的栈；然后需要对变量进行重置；
- ']'处理：意味着当前的子字符串已经结束。弹出栈顶的重复次数，重复当前的字符串（栈顶），并与之前的（解码好的）字符串拼接起来。
- 最好返回拼接的字符串。

具体实现代码(详解版）：

class Solution {
public:string decodeString(string s) {stack<int> count_stack;    // 用于存储重复的次数stack<string> string_stack; // 用于存储部分解码后的字符串string current_string = ""; // 当前构建的解码字符串int current_num = 0;        // 当前重复次数for (char c : s) {if (isdigit(c)) {// 如果是数字，构建重复的次数current_num = current_num * 10 + (c - '0');} else if (c == '[') {// 遇到 '['，保存当前重复次数和当前字符串count_stack.push(current_num);string_stack.push(current_string);current_string = ""; // 重置当前字符串current_num = 0;     // 重置重复次数} else if (c == ']') {// 遇到 ']'，进行解码操作string temp = current_string;current_string = string_stack.top(); // 获取上一个字符串string_stack.pop();int repeat_times = count_stack.top(); // 获取重复次数count_stack.pop();// 重复当前字符串，并拼接到之前的字符串for (int i = 0; i < repeat_times; i++) {current_string += temp;}} else {// 如果是字母，直接加入当前字符串current_string += c;}}return current_string;}
};

4每日温度

在这里插入图片描述
思路分析：我们需要找出每一天之后温度更高的那一天的天数。我们可以使用一个单调递减栈来解决这个问题。

栈的维护：栈中存储的是温度的索引。栈中的元素按温度从大到小排列，即栈顶元素所对应的温度是当前元素中最小的。
遍历温度数组：对于当前天数的温度 temperatures[i]，我们不断与栈顶索引对应的温度比较，若当前温度大于栈顶温度对应的温度，则说明找到了栈顶温度的下一个更高温度，弹出栈顶元素并计算天数差。
更新栈：无论是否弹出栈顶元素，当前天数的索引都会被压入栈中。

具体实现代码（详解版）

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> answer(n, 0);  // 初始化为 0，表示没有找到更高温度的天数stack<int> stk;  // 栈用于存储温度的索引,即第几天for (int i = 0; i < n; ++i) {// 比较当前温度与栈顶温度的大小while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {int idx = stk.top();  // 弹出栈顶元素的索引stk.pop();answer[idx] = i - idx;  // 计算天数差并更新 answer 数组}stk.push(i);  // 将当前天数的索引压入栈中}return answer;}
};

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

5.柱状图中最大的矩形

在这里插入图片描述
思路分析：我们可以使用单调栈（Monotonic Stack）的方法，利用栈来优化查找每个柱子能够构成的最大矩形面积。

维护一个单调递增的栈：栈中保存的是柱子的索引，并且栈中的柱子高度是单调递增的。这样可以确保在遍历柱子时，我们可以快速地找到当前柱子能够形成的矩形的宽度
遍历柱子高度：
- 对于没应该柱子，检查它和栈顶柱子相比是否能够构成更大的矩形；
- 如果当前柱子的高度大于栈顶柱子的高度，直接将当前柱子的索引压入栈中；
- 如果当前柱子的高度小于栈顶柱子的高度，说明栈顶柱子已经找到了它更构成的最大矩形，应该弹出栈并计算矩形的面积。面积的计算需要使用当前柱子的索引来确定宽度，具体的：
  - 如果栈为空，说明当前栈顶柱子从第一个柱子开始，到当前柱子的宽度是 i；
  - 否则，矩形的宽度是当前柱子索引 i 和栈顶元素索引之间的差值减去 1。
处理完所有柱子之后，栈中可能还剩下未处理的柱子，它们的右边界已经到达数组的末尾。需要依次弹出栈中的元素并计算面积；
面积计算：每次弹出栈顶元素时，计算该元素作为矩形的高，并且矩形的宽度由当前索引和栈顶元素之前的索引差值来确定。

具体实现代码（详解版）：

class Solution {
public:int largestRectangleArea(vector<int>& heights) {stack<int> stk;  // 单调递增栈，用来存储柱子的索引int max_area = 0;  // 最大矩形面积heights.push_back(0);  // 在末尾添加一个 0，确保栈能最终被清空for (int i = 0; i < heights.size(); ++i) {// 当前柱子的高度小于栈顶柱子的高度时，计算面积while (!stk.empty() && heights[i] < heights[stk.top()]) {int h = heights[stk.top()];  // 弹出栈顶元素，作为矩形的高stk.pop();int width = stk.empty() ? i : i - stk.top() - 1;  // 宽度由当前索引和栈顶索引差值决定max_area = max(max_area, h * width);  // 更新最大面积}stk.push(i);  // 将当前柱子的索引压入栈中}return max_area;  // 返回最大矩形面积}
};

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

单调栈是处理一类问题的强大工具，特别是与区间、顺序、范围、最大/最小值相关的题目。它的本质是维护栈中元素的顺序关系，使得栈中的元素满足某种单调性（单调递增或单调递减）。使用单调栈的主要目的是高效地查找满足条件的区间或值，从而减少了暴力解法中的时间复杂度。

单调栈常见步骤：

初始化栈：根据问题的需求，通常是存储元素的索引，有时也存储元素本身；
遍历数组：
- 对于每个元素，检查栈顶的元素是否满足特定的条件（例如，是否大于或小于当前元素）
- 如果满足条件，就弹出栈顶元素，并进行相关的计算（如更新最大面积或存储下一个更大面积的索引）
- 如果不满足条件或栈为空，将当前元素索引入栈
边界条件的处理：对于某些问题，最后可能栈中回残留一些未处理的元素，需要在遍历完成之和进行额外的计算（如计算剩余的矩形面积）

单调栈的核心思想是维护一个单调递增或单调递减的栈，通过栈的特点来高效处理一些需要查找、比较或计算区间最大值/最小值的问题。掌握如何使用单调栈来解决问题，可以帮助在算法中高效地处理一些常见的难题，并优化暴力解法的时间复杂度。

查看全文

http://www.mrgr.cn/news/67809.html