算法篇：栈之常见题型

灰子学技术

发布于 2020-09-07 15:19:13

2570

发布于 2020-09-07 15:19:13

算法：

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

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]
}

执行结果：