您现在的位置是：首页 > 文章详情

算法篇：栈之常见题型

日期：2020-08-30点击：352收藏

算法：

栈算是比较常见的一种数据结构，先进后出，一般操作步骤如下：

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 []byte for _, d := range cc { if d == '(' || d== '{' || d == '[' { satckStr = append(satckStr,d) } else {        // ),],}这几个符号需要判断合法性 last := len(satckStr)-1 if 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,0 var stacks []byte for 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 []int Mins []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)-1 if 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]}