每日两题 / 20. 有效的括号 155. 最小栈（LeetCode热题100）

20. 有效的括号 - 力扣（LeetCode）

遇到左括号入栈
遇到右括号判断栈顶是否为匹配的左括号
最后判断栈是否为空

func isValid(s string) bool {var stk []runefor _, value := range s {if value == '(' || value == '{' || value == '[' {stk = append(stk, value)} else if (len(stk) == 0) {return false } else {topchar := stk[len(stk) - 1]stk = stk[:len(stk) - 1]if topchar == '(' && value != ')' {return false } else if topchar == '{' && value != '}' {return false } else if topchar == '[' && value != ']' {return false }}}return len(stk) == 0
}

---

155. 最小栈 - 力扣（LeetCode）

要在$O(1)$的时间找出最小数，一定需要额外的空间保存信息，这里使用一个辅助栈维护额外的信息
根据栈的先进后出性质，push一个数后，如果该数大于最小数，那么之后获取的最小数一定不是该数，所以无需额外记录该大数的信息。向辅助栈push当前最小数（辅助栈的栈顶）
如果该数小于最小数，那么之后获取的最小数就是该数，需要额外记录该数的信息。向辅助栈push该数
pop操作时，同时pop两个栈的栈顶

type MinStack struct {stk []intmin_stk []int 
}func Constructor() MinStack {return MinStack{stk: []int{},min_stk: []int{},}
}func (this *MinStack) Push(val int)  {this.stk = append(this.stk, val) if len(this.min_stk) == 0 {this.min_stk = append(this.min_stk, val)} else if val > this.min_stk[len(this.min_stk) - 1] {this.min_stk = append(this.min_stk, this.min_stk[len(this.min_stk) - 1])} else {this.min_stk = append(this.min_stk, val)}
}func (this *MinStack) Pop()  {this.stk = this.stk[:len(this.stk) - 1]this.min_stk = this.min_stk[:len(this.min_stk) - 1]
}func (this *MinStack) Top() int {return this.stk[len(this.stk) - 1]
}func (this *MinStack) GetMin() int {return this.min_stk[len(this.min_stk) - 1]
}/*** Your MinStack object will be instantiated and called as such:* obj := Constructor();* obj.Push(val);* obj.Pop();* param_3 := obj.Top();* param_4 := obj.GetMin();*/