DEV Community
·
力扣题解 #6
💡
原文英文，约600词，阅读约需2分钟。
📝
内容提要
这篇文章介绍了两个问题的解决方案。第一个问题是设计一个支持push、pop、top和获取最小元素的栈，要求每个操作的时间复杂度为O(1)。解决方案是使用两个栈，一个存储所有值，一个存储最小值。第二个问题是计算逆波兰表达式的值，使用栈来存储结果和操作数，根据操作符进行计算。
🎯
关键要点
- 设计一个支持push、pop、top和获取最小元素的栈，要求每个操作的时间复杂度为O(1)。
- 使用两个栈，一个存储所有值，另一个存储最小值。
- 在push函数中，如果min栈为空或新值小于等于当前最小值，则将新值添加到min栈。
- 在pop函数中，如果s1栈的顶部值等于min栈的顶部值，则从min栈中弹出顶部值。
- 在top函数中，返回s1栈的顶部值。
- 在getMin函数中，返回min栈的顶部值。
- 计算逆波兰表达式的值，使用栈来存储结果和操作数。
- 有效的操作符包括'+', '-', '*', 和 '/'，每个操作数可以是整数或另一个表达式。
- 在遍历tokens时，如果字符是操作数，则将其推入栈中；如果是操作符，则弹出两个元素并执行操作。
- 最终结果位于栈的顶部。
➡️
