2024.06.26 刷题日记

20. 有效的括号

利用栈:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
bool isValid(string s) {
std::map<char, int> m = {{'(', -1}, {')', 1}, {'{', -2},
{'}', 2}, {'[', -3}, {']', 3}};
stack<char> st;
for (auto c : s) {
!st.empty() && m[st.top()] < 0 && m[st.top()] + m[c] == 0
? st.pop()
: st.push(c);
}
return st.empty();
}
};

155. 最小栈

核心思路是,要保证辅助栈的 top 永远是当前栈的最小值:

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
class MinStack {
public:
MinStack() { // 初始化时可以将一个极大值推入 min 栈作为哨兵值,简化代码逻辑
min.push(INT_MAX);
}

void push(int val) {
st.push(val);
// 无论如何都将当前最小值推入min栈
min.push(std::min(min.top(), val));
}

void pop() {
st.pop();
min.pop();
}

int top() { return st.top(); }

int getMin() { return min.top(); }

private:
stack<int> st;
stack<int> min;
};

/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/

总结

这两道题都充分利用了栈的特性来解决问题。栈是一种后进先出(LIFO)的数据结构,适合用于解决需要最近相关性的问题,如括号匹配和动态追踪最小值。

1. 有效的括号(LeetCode 20)

核心思路

  • 利用栈来处理所有的括号匹配问题。左括号时压栈,右括号时判断栈顶元素是否匹配,匹配则出栈,不匹配则压栈。
  • 使用 std::map 来存储括号字符及其对应的数值,其中左括号为负值,右括号为正值。这样可以通过相加判断括号是否配对。

关键实现

  • 遍历字符串中的每个字符。
  • 检查当前字符与栈顶字符是否构成一对有效的括号,若是,则弹出栈顶;若否,将当前字符压入栈。
  • 最后,栈空则表示所有括号正确匹配,否则表示有未匹配的括号。

2. 最小栈(LeetCode 155)

核心思路

  • 维护两个栈:一个是主栈 st 存储所有元素,另一个是辅助栈 min 用于存储当前最小值。
  • 每次元素入栈时,同时更新辅助栈的栈顶元素为当前最小值。

关键实现

  • 每次入栈操作,将元素推入主栈的同时,比较该元素与辅助栈顶元素,将较小值推入辅助栈。
  • 出栈操作时,两个栈同时弹出顶部元素,这样可以保证辅助栈顶总是对应主栈中所有元素的最小值。
  • 获取最小值操作直接返回辅助栈的栈顶元素,因为它始终是当前所有元素的最小值。

核心思想总结

这两道题目通过栈结构的使用展示了如何有效地管理和查询数据,同时也突出了辅助数据结构(如辅助栈和哈希表)在解决问题中的重要作用。在设计数据结构或算法时,保持结构的一致性和操作的同步性是非常关键的。对于 “有效的括号”,重点在于匹配和消除过程;而对于 “最小栈”,重点在于保持最小值的实时更新和有效获取。这两种方法都优雅地利用了栈的基本操作来解决问题,展示了栈在算法设计中的强大能力和灵活性。


2024.06.26 刷题日记
http://blog.luliang.online/2024/06/26/2024.06.26 刷题日记/
作者
Luyoung
发布于
2024年6月26日
许可协议