深圳网站建设seo优化,东凤网站建设,太仓营销型网站建设,哪里网站建设公司比较好目录
0.前言
1.最小栈
1.1 原题展示
1.2 思路分析
1.2.1 场景引入
1.2.2 思路
1.3 代码实现
1.3.1 最小栈的删除
1.3.2 最小栈的插入
1.3.3 获取栈顶元素
1.3.4 获取当前栈的最小值
2. 有效的括号 0.前言 本篇博客已经把两个关于栈的OJ题分块#xff0c;可以根据目…
目录
0.前言
1.最小栈
1.1 原题展示
1.2 思路分析
1.2.1 场景引入
1.2.2 思路
1.3 代码实现
1.3.1 最小栈的删除
1.3.2 最小栈的插入
1.3.3 获取栈顶元素
1.3.4 获取当前栈的最小值
2. 有效的括号 0.前言 本篇博客已经把两个关于栈的OJ题分块可以根据目录跳转并且代码已经上传至gitee可自取。 1.最小栈
155. 最小栈 - 力扣LeetCode
1.1 原题展示 本题需要我们设计一个栈这个栈相对于普通的栈有一个特异功能可以在常数O1的时间复杂度下直接找到并返回现在栈内所有元素的最小值是多少。 这个要设计的有特异功能的栈我们称之为最小栈本题就是要实现一个MinStack类。多了一个特异接口getMin。 1.2 思路分析
1.2.1 场景引入 我们如何实时记录当前栈的最小值呢有人说我们可以在MinStack类当中记录一个int _min成员每次插入之后我们对比一下这个_min如果插入的数据比当前的_min更小的话那就更新_min这样不就可以实时记录当前最小值吗 class MinStack {
private:stackint _st;int _min;
}; 但是这样并不能的哦如果你删除数据呢如果你删除一个当前的_min值元素那你能知道现在删除完_min元素之后栈的新最小值_min是什么需要更新什么值呢这就不知道了吧 所以我们的思路是再存一个存放最小值的容器这个容器负责存储如果每次删除完_min最小值之后可以从这个容器当中再找到次小的_min的值。 从时序角度上来说一个栈的最小值肯定是一浪更比一浪强前浪被拍在沙滩上。在插入数据的过程中一个栈内数据的最小值是不断的被更新成越来越小的。相反在删除数据的过程中如果我们删除了现在的最小值后浪我们应该把曾经作为最小值的值被拍死的前浪作为新的最小值。 栈这个容器是后进先出先进后出我们的记录的最小值先被作为最小值被拍死的前浪们的元素是后出的最新一次作为最小值的元素肯定是优先被删除的后成为最小值的值要先出。所以我们选取栈作为记录每次最小值的容器。 class MinStack {
private:stackint _st;stackint _min_st;
1.2.2 思路 所以我们除了定义一个主栈_st存储所有插入的数据还要定义一个最小栈_min_st用来存储每次当前栈的最小值始终维持这个最小栈的栈顶元素始终代表当前的最小值。 如果我们在主栈当中插入一个比当前栈最小值_min还要更小的一个数据more min那么我们就在最小栈当中插入以记录这个更小的一个数据。而如果是一个插入更大的数据那就没有必要动最小栈_min_st此时最小值不变。 如果我们在主栈当中删除了当前栈的最小值那么我们也要在最小栈进行出栈操作去除更新当前的最小值出栈之后那接下来最小栈的栈顶就变成了次小的最小值此时最小栈的栈顶仍然代表着当前栈的最小值 1.3 代码实现
1.3.1 最小栈的删除 最小栈的栈顶数据代表当前栈内所有数据的最小值如果删除的是当前最小值那要顺便再对最小栈出栈更新为次小值为最小值 void pop() {//我们删除还要看删除的是否在现在的最小栈中int val _st.top();if(val _min_st.top()) //是最小栈的该元素要删除{_st.pop();_min_st.pop();}else //不是最小栈中的元素就可以直接出栈,然后现在min_st中的顶还是最小值{_st.pop();}}
1.3.2 最小栈的插入 插入比当前最小值更小的数据更新入栈_min_st或者还有一种特殊情况如果是一个空栈我们也要更新入栈_min_st 如果插入比当前最小值还大的数据那么我们就没有必要动最小栈_min_st。 而如果插入的是和当前最小值相等的数据那么我们入不入最小栈呢不管入不入栈都不会影响当前栈的最小值的记录这样看入不入的确没有太大关系。可是你想一想如果你遇到相等最小值的时候不入最小栈的话在删除逻辑中如果你删除了这个最小值那么我们如果出栈_min_st那此时最小栈的栈顶元素就不能代表当前栈内元素的最小值了。 例如你依次插入了 2 3 4 1 1那最小栈从栈底到栈顶就依次是2 1如果我要删除1那主栈内就变为2 3 4 1那我最小栈就会变成2此时最小栈栈顶就不是当前栈的最小值。 所以如果插入的是和当前最小值相等的数据也要入最小栈。 void push(int val) {_st.push(val);if(_min_st.empty()){_min_st.push(val);}else //不是空{//如果出现了更小的val那就入栈if(val_min_st.top()) //相等的情况也必须入栈不然我们删除的时候就不知道最小值在栈底还有多个的情况{_min_st.push(val);}//否则更大的val就不用入栈了}}
1.3.3 获取栈顶元素 返回主栈的栈顶。 int top() {return _st.top();}
1.3.4 获取当前栈的最小值 返回最小栈的栈顶。 int getMin() {return _min_st.top();}
2. 有效的括号
20. 有效的括号 - 力扣LeetCode 就是给你一个括号序列看看这个是否是一个有效的括号序列。那么什么是有效的括号呢其实就是最近的一个左括号和离得它最近的右括号能够相互匹配也可以说是一个右括号和离得它最近的左括号能够相互匹配匹配的意思是 ( 只能去匹配 ) { 只能去匹配 } [ 只能去匹配 ] 这里用栈结构即可很好的解决如果遇到了左括号那么就入栈等待最近一个右括号的匹配先进后出后进先出一定是后面的左括号先被匹配前面的括号后被匹配这完美的符合栈的性质如果遇到了右括号那么我们就出栈顶数据即找到最近的一个左括号进行匹配检查如果不匹配那就return false如果匹配就继续检查。 转换成代码就是这样的 bool isValid(char * s){此时就可以利用栈先进后出的特性进行判断*///遍历遇到左括号则入栈//遍历遇到右括号则出栈数据对右括号进行匹配//到最后遍历匹配完毕栈为空即可【这是针对左括号多出来的情况】//【而右括号多出来的情况则是栈中没有数据与之匹配了此时也不是有效的括号false】//定义一个栈Stack st;StackInit(st);//遍历字符串括号集while(*s!\0){//遇到左括号if(*s { || *s [ || *s(){StackPush(st,*s);}else{//遇到右括号//判断非法情况,右括号多余左括号if(StackEmpty(st)){return false;}//出栈和右括号进行匹配int left_brace StackTop(st);StackPop(st);//不匹配则false匹配则继续遍历比较if(left_brace{*s ! }|| left_brace[*s ! ]|| left_brace(*s ! )){return false;}}s;}//判断非法情况,左括号多余右括号return StackEmpty(st);
} 当然我们还需要想一想左右括号如果数量不匹配的情况到最后遍历匹配完毕如果栈为空那就是左右括号全部被匹配成功而如果栈不为空这是针对左括号数量多于右括号的情况而右括号多出来的情况则是栈中没有数据与之匹配了此时也不是有效的括号false。
