好了，说够了，可以开始了。
知识点- 栈是一种逻辑结构，特点是只能在一端进行 *** 作，元素先进后出。
- C++
- push() 元素入栈
- pop() 元素出栈
- top() 读取栈顶元素
- empty() 判断栈是否为空
- python
- append() ：元素入栈
- pop()：元素出栈并返回
- stack[-1]：返回栈顶元素
题目来源：剑指Offer
学习计划：30 in 30
「剑指 Offer」 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台
一、剑指 Offer 09. 用两个栈实现队列
1. C++版本 核心点- 一个栈作为输入输出栈，一个栈作为辅助栈。
- 简化代码的关键点：如何减少元素在两个栈之间的交换次数。
使用一个整型变量size，记录栈内的元素个数。判断栈是否为空的时候，用size==0是否成立来进行 *** 作。比调用empty()函数效率更高。
具体C++代码如下：
//c++版本
class CQueue {
public:
stack stack1; //定义两个栈stack1，stack2
stack stack2;
int size=0; //用来记录逻辑上的队列的长度，即两个栈中所有元素的个数总和
CQueue() {}
void appendTail(int value) { //需要在逻辑队尾添加元素，直接添加到栈1中
stack1.push(value);
size++;
}
int deleteHead() {
if(size==0) //逻辑队列此时为空
{
return -1;
}
else
{
if(stack2.empty()) //辅助栈中元素已经全部输出
{
while(!stack1.empty()) //如果栈1中仍然有元素
{
int tmp=stack1.top(); //将栈1中元素逐个输入到栈2中
stack1.pop();
stack2.push(tmp);
}
}
size--;
int res=stack2.top();
stack2.pop();
return res;
}
}
}; - 理解栈与队列的存储、读取逻辑差异所在：先入后出与先入先出；
- 理解两栈首尾相接等于队列的逻辑合理性。
- 理清何时将输入栈的元素压入输出栈，并用代码实现；
- 梳理完全 输入栈与输出栈 各自是否为空的几种情况，不要遗漏可能性，以致报错。
- 出入栈：
入栈：stack.append() ;
出栈：stack.pop()【注意：pop方法不只是输出栈顶元素，而且会将其删除】
- 关于python中的self：
1. python中的self - 不妨不妨，来日方长 - 博客园
2. 一篇文章让你彻底搞清楚Python中self的含义 - jessonsh - 博客园
#python3版本
class CQueue:
## 定义两个栈，通过命名可直观知道一个实现输入功能，一个实现输出功能
def __init__(self):
self.stack_in=[]
self.stack_out=[]
## 输入功能的实现很符合直觉理解，记住append()方法。
def appendTail(self, value: int) -> None:
self.stack_in.append(value)
## 输出要分三种情况分析：
## 1。输出栈B中非空；2。输出栈B为空，输入栈A非空；3。输出栈B与输入栈A均为空。
def deleteHead(self) -> int:
if self.stack_out :
return self.stack_out.pop()
## 1。直接从B中输出栈顶元素并删除，即pop()方法；
elif self.stack_in :
while self.stack_in :
self.stack_out.append(self.stack_in.pop())
return self.stack_out.pop()
## 2。将A中元素全部压入输出栈B中。注意，这是从逆序转为顺序的关键。
else :
return -1
## 3。返回-1二、 剑指 Offer 30. 包含min函数的栈
1. C++版本 第一次尝试的错误思路及代码：最初的思路：用变量x记录当前的最小元素的值，此外并未采用任何结构记录最小值。
Bug：如果d出的元素是当前的最小值，那么在元素d出后，剩余元素中的最小值无法在O(1)的时间复杂度内找到。
正确的思路：设计辅助栈辅助栈：栈中元素个数与当前输入栈的元素个数相同（非边界情况下），区别在于，辅助栈的每一个元素，都对应于输入栈中同等高度的当前最小元素。当需要输出最小元素时，同时输出辅助栈和输入栈中的栈顶元素。
关键点考虑边界情况，当第一次输入元素时，此时尚未存在最小元素，如何确定辅助栈中栈顶元素？在初始化的时候，将int类型的最大值，放入到辅助栈中，作为边界条件。在执行代码时，第一个输入的元素会被记为当前最小的元素。
动图源于Leetcode网站官方题解（力扣）
//c++版本
class MinStack {
public:
/** initialize your data structure here. */
//
stack instack;
stack minstack; //辅助栈
MinStack() {
minstack.push(INT_MAX); //将int类型的最大值放在辅助栈的栈底，作为边界条件
}
void push(int x) {
int tmp=minstack.top();
if(x 如何在O(1)时间复杂度内实现min函数
#python版本
class MinStack:
def __init__(self):
self.A , self.B = [] , []
def push(self, x: int) -> None:
self.A.append(x)
## 若栈B中为空，或者x比栈顶元素更小，就把x压入栈。
## 即，保证栈B的顶上元素为最小值。
if not self.B or self.B[-1] >= x :
self.B.append(x)
def pop(self) -> None:
## 输出并删除栈A的栈顶元素的同时，进行判断：
## 若此元素为当前最小值（即B的栈顶元素），那么这边也需要同步删除！
if self.A.pop() == self.B[-1] :
self.B.pop()
def top(self) -> int:
return self.A[-1]
def min(self) -> int:
return self.B[-1]三、 20. 有效的括号
1. C++版本 思路括号匹配问题是栈的应用的经典问题，主要思路在于使用栈保存左括号，当扫描到右括号的时候，可以分类讨论一下三种情况：
①栈内的栈顶元素正好是匹配的符号：d出栈顶元素，一对匹配完成
②栈内元素与当前扫描到的元素不匹配：匹配失败
③栈空：说明不存在左括号与当前元素匹配。匹配失败
当从前到后扫描完所有的元素后，如果栈仍然不为空，说明有部分左括号没有匹配完成。匹配失败
如果栈为空，那么匹配成功。
//c++版本
class Solution {
public:
bool isValid(string s) {
char ch;
stack instack;
for(int i=0;i 利用栈顶元素为最近一个压入元素的特性，进行邻近括号的匹配
难点空栈情况的考虑；字典的运用
小章's Codeclass Solution:
def isValid(self, s: str) -> bool:
## 首先定义栈A
self.A = []
for i in s :
## 如果遍历到左括号，将该元素压入栈A中
if i in ('(' ,'[' ,'{') :
self.A.append(i)
## 善用continue跳出此次判断，避免内存浪费
continue
## 如果遍历到右括号，需要考虑其是否与栈顶元素配对成功。额外需要注意的是栈为空的情况，也是错误的！
elif i == ')' :
if not self.A or self.A.pop() != '(' :
return False
else :
continue
elif i == ']' :
if not self.A or self.A.pop() != '[' :
return False
else :
continue
elif i == '}' :
if not self.A or self.A.pop() != '{' :
return False
else :
continue
## 最后，特别需要注意！单独余一个多的左括号，也是不合规的！所以最后要把这种情况排除掉！
return (len(self.A) == 0)class Solution:
def isValid(self, s: str) -> bool:
## 首先定义栈A，并给它一个初始值，与题中元素不干扰，用于保证不出现空栈的异常情况。【一个小技巧】
self.A = ['?']
## 然后定义字典。键为左括号，值为右括号。
dic = {'?':'?', '(':')', '[':']', '{':'}'}
## 如果是字典中的键，就压入栈
for i in s :
if i in dic :
self.A.append(i)
## 如果是字典中的值，能和栈顶元素配对的，就pop出来，假装消消乐了；
## 如果对不上，就报错
elif :
dic[self.A.pop()] != i :
return False
## 最后同样要避免剩下落单的左括号的情况，所以需要判定是否栈恢复如初。
return (len(self.A) == 1)四. 735. 行星碰撞
1.C++版本：先鸽了，我还没有彻底搞懂，搞懂了下一次补上。 2. python版本（小章写的！俺的室友老棒了！）class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
## 首先定义一个栈A
self.A = []
for i in asteroids :
## 如果栈为空，需要先将第一个行星压入栈
if not self.A :
self.A.append(i)
continue
## 如果下一颗行星和当前这颗行星互相靠近,即向左和向右的关系时，判断一下哪颗爆炸boom
elif i < 0 and self.A[-1]> 0 :
current = self.A[-1]
## 如果两颗一样大，就把现在的炸了，新的忽视（相当于也炸了）
if abs(i) == current :
self.A.pop()
## 如果下一颗更小，就忽视
elif abs(i) < current :
continue
## 如果下一颗更大，需要循环判断撞到啥时候结束
else :
self.A.pop()
is_i_destroyed = 0
while self.A and self.A[-1] > 0 and is_i_destroyed == 0:
updated_current = self.A[-1]
if updated_current < abs(i) :
self.A.pop()
continue
if updated_current == abs(i) :
self.A.pop()
is_i_destroyed = 1
continue
else :
is_i_destroyed = 1
continue
if is_i_destroyed == 0:
self.A.append(i)
else :
self.A.append(i)
return self.A
其实思路是一样的，但是这个解法抓住了更核心的问题，而且代码语言高度提炼
还有很巧妙的地方，我会分三种情况写，但三叶的这种写法就只需要两种情况，纯1、纯2、both 1和2 即为第三种情况。
妙啊~~~
class Solution:
def asteroidCollision(self, ats: List[int]) -> List[int]:
stk = []
for t in ats:
ok = True
while ok and stk and stk[-1] > 0 and t < 0:
a, b = stk[-1], -t
##1。
if a <= b:
stk.pop(-1)
##2。
if a >= b:
ok = False
if ok:
stk.append(t)
return stkp.s. 虽然我俩写的都是很简单的题目，但是还是选择发出来，不仅是为了以后可以时常复习，也算是彼此督促相互监督。学无止境，都给我学！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）