算法篇：栈之常见题型
算法：
栈算是比较常见 的一种数据结构，先进后出，一般操作步骤如下：
1. 建立一个栈，golang中往往使用slice来操作2. 满足条件的元素入栈3. 出栈的时候一般都是最后一个入栈的元素，这里需要调节元素的位置
题目1: 有效的括号
https://leetcode-cn.com/problems/valid-parentheses/
代码实现：
func isValid(s string) bool {if len(s)%2 == 1 {return false}cc := []byte(s)var satckStr []bytefor _, d := range cc {if d == '(' || d== '{' || d == '[' {satckStr = append(satckStr,d)} else {// ),],}这几个符号需要判断合法性last := len(satckStr)-1if ok := popStrOk(d,satckStr,last); !ok {return false}satckStr = satckStr[:last]}}if len(satckStr) != 0 {return false}return true}func popStrOk(d byte, satckStr []byte, last int) bool{if len(satckStr) == 0 {return false}switch d {case ')':if satckStr[last] != '(' {return false}case ']':if satckStr[last] != '[' {return false}case '}':if satckStr[last] != '{' {return false}default:return false}return true}/*解题思路：用栈来操作1.先初步过滤掉数据，将奇数的字符串丢掉2.遍历字符串，将(,[,{入栈3.右括号出栈，判断是否有对应的做括号匹配(备注：考虑栈为空的时候)4.都处理完了，栈非空为false,否则为true*/
执行结果：
题目2: 删除最外层的括号
https://leetcode-cn.com/problems/remove-outermost-parentheses/
代码实现：
func removeOuterParentheses(S string) string {strs := []byte(S)len := len(strs)L,R := 0,0var stacks []bytefor i := 0; i < len; i++{if strs[i]=='(' {L++} else {R++}if R != L && L != 1{ // L==1表示的是最左边的左括号stacks =append(stacks,strs[i])} else if R == L { // 这个是最右边的右括号，不入栈L,R = 0,0}}return string(stacks)}/*栈实现：利用左右括号的数量相同条件，L == R的时候，表示的是找到了源语句L！=R的时候，进行入栈，不过记得不要将最开始的左括号和最右边的右括号入栈*/
执行结果：
题目3: 最小栈
https://leetcode-cn.com/problems/min-stack/
代码实现：
/*关键点是最小值的获取，用栈Mins作为一个有序数列，最后一位表示的是最小值，以第一次入栈的元素作为标识，后续进来的元素小于等于它，放到数组末尾。出栈的时候，只有出栈的数据是小于等于Mins中的最小元素的，才会出栈备注：注意第一个入栈元素是必须要入栈的*/type MinStack struct {Arr []intMins []int}/** initialize your data structure here. */func Constructor() MinStack {return MinStack{}}func (this *MinStack) Push(x int) {this.Arr = append(this.Arr,x)if len(this.Mins) == 0 || x <= this.Mins[len(this.Mins)-1] {this.Mins = append(this.Mins,x)}return}func (this *MinStack) Pop() {if len(this.Arr) == 0 {return}last := len(this.Arr)-1if this.Arr[last] <= this.Mins[len(this.Mins)-1] {this.Mins = this.Mins[:len(this.Mins)-1]}this.Arr = this.Arr[:last]return}func (this *MinStack) Top() int {return this.Arr[len(this.Arr)-1]}func (this *MinStack) GetMin() int {return this.Mins[len(this.Mins)-1]}
执行结果：
本文分享自微信公众号 - 灰子学技术（huizixueguoxue）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
