20. 有效的括号 - 力扣（LeetCode）
栈：先入后出的
从前往后遍历，如果是左括号，入栈；如果是右括号，尝试和前面的左括号配对，配对的话出栈；否则，直接返回。
func isValid(s string) bool {
var stack []byte
for i := 0; i < len(s); i++ {
switch s[i] {
case '(', '{', '[':
//入栈
stack = append(stack, s[i])
case ')':
if len(stack) > 0 && stack[len(stack)-1] == '(' {
//配对 出栈
stack = stack[:len(stack)-1]
} else {
return false
}
case ']':
if len(stack) > 0 && stack[len(stack)-1] == '[' {
//配对 出栈
stack = stack[:len(stack)-1]
} else {
return false
}
case '}':
if len(stack) > 0 && stack[len(stack)-1] == '{' {
//配对 出栈
stack = stack[:len(stack)-1]
} else {
return false
}
}
}
return len(stack) == 0
}71. 简化路径 - 力扣（LeetCode）
先把所有的路径分隔出来放到paths数组里，如果当前路径是.的话，跳过；如果是..并且上一个路径不为空的话，去掉上一个路径；否则，加入paths数组
func simplifyPath(path string) string {
paths := make([]string,0,5)
for i := 0; i < len(path); {
if path[i] == '/' {
i ++
}else{
//维护现在路径
var now []byte
for i < len(path) && path[i] != '/' {
now = append(now,path[i])
i ++
}
nowStr := string(now)
if nowStr == "." {
continue
}else if nowStr == ".." && len(paths) > 0 {
paths = paths[:len(paths)-1]
}else if nowStr != ".." && nowStr != "." {
paths = append(paths,nowStr)
}
}
}
var ans string
if len(paths) == 0 {
return "/"
}
for _,path := range paths {
ans = ans + "/" + path
}
return ans
}155. 最小栈 - 力扣（LeetCode）
额外用一个栈维护当前的最小元素 push的时候，如果stackMin为空或是当前元素更小，就push进去
type MinStack struct {
//额外用一个栈维护最小元素
stack []int
stackMin []int
}
func Constructor() MinStack {
return MinStack{
stack:[]int{},
stackMin:[]int{},
}
}
func (this *MinStack) Push(val int) {
this.stack = append(this.stack,val)
if len(this.stackMin) == 0 || this.stackMin[len(this.stackMin)-1] >= val {
this.stackMin = append(this.stackMin,val)
}
}
func (this *MinStack) Pop() {
if len(this.stack) == 0 {
return
}
val := this.stack[len(this.stack)-1]
this.stack = this.stack[:len(this.stack)-1]
if len(this.stackMin) > 0 && this.stackMin[len(this.stackMin)-1] == val {
this.stackMin = this.stackMin[:len(this.stackMin)-1]
}
}
func (this *MinStack) Top() int {
return this.stack[len(this.stack)-1]
}
func (this *MinStack) GetMin() int {
return this.stackMin[len(this.stackMin)-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();
*/394. 字符串解码 - 力扣（LeetCode）
维护数字栈和字符串栈，如果当前字符是数字的话，累加到tmpNum里；如果当前字符是字母的话，累加到tmpStr里
如果是左括号，把前面的数字和字符都入栈
如果是右括号，将前面的栈顶数字取出来，对于栈顶字符串做累加tempStr的操作，并更新tempStr
func decodeString(s string) string {
var stackNum []int
var stackStr []string
var tmpStr string
var tmpNum int
for i := 0 ; i < len(s); i ++ {
if s[i] >= '0' && s[i] <= '9' {
tmpNum = tmpNum * 10 + int(s[i]-'0')
}else if (s[i] >= 'a' && s[i] <= 'z' ) || (s[i] >= 'A' && s[i] <= 'Z') {
tmpStr += string(s[i])
}else if s[i] == '[' {
//把前面的入栈
stackNum = append(stackNum,tmpNum)
tmpNum = 0
stackStr = append(stackStr,tmpStr)
tmpStr = ""
}else{
//遇到]
now := stackNum[len(stackNum)-1]
stackNum = stackNum[:len(stackNum)-1]
for j := 0; j < now; j ++ {
stackStr[len(stackStr)-1] = stackStr[len(stackStr)-1]+tmpStr
}
tmpStr = stackStr[len(stackStr)-1]
stackStr = stackStr[:len(stackStr)-1]
}
}
return tmpStr
}150. 逆波兰表达式求值 - 力扣（LeetCode）
没有括号所以直接模拟即可，注意除法和减法的顺序，是a-b还是b-a
func evalRPN(tokens []string) int {
var stack []int
for _,token := range tokens {
// fmt.Println(token,stack)
switch token {
case "+":
a := stack[len(stack)-1]
stack = stack[:len(stack)-1]
b := stack[len(stack)-1]
stack = stack[:len(stack)-1]
stack = append(stack,a+b)
case "-":
a := stack[len(stack)-1]
stack = stack[:len(stack)-1]
b := stack[len(stack)-1]
stack = stack[:len(stack)-1]
stack = append(stack,b-a)
case "/":
a := stack[len(stack)-1]
stack = stack[:len(stack)-1]
b := stack[len(stack)-1]
stack = stack[:len(stack)-1]
stack = append(stack,b/a)
case "*":
a := stack[len(stack)-1]
stack = stack[:len(stack)-1]
b := stack[len(stack)-1]
stack = stack[:len(stack)-1]
stack = append(stack,a*b)
default:
tokenInt,_ := strconv.Atoi(token)
stack = append(stack,tokenInt)
}
}
return stack[0]
}单调栈
算法数据结构——关于单调栈（Monotone Stack）的详细讲解及应用案例-CSDN博客
496. 下一个更大元素 I - 力扣（LeetCode）
对nums2构造单调递增栈求解下一个更大的元素
使用哈希表来存储 nums2[j]的下一个更大元素的值
映射
单调递增栈指的是数组是降序数组，栈底是数组开始，栈顶是数组结尾
func nextGreaterElement(nums1 []int, nums2 []int) []int {
var stack []int
mp := make(map[int]int,len(nums2))
//倒序遍历
for i := len(nums2) - 1; i >= 0; i -- {
x := nums2[i]
//先出栈
for len(stack) > 0 && x >= stack[len(stack)-1] {//说明栈顶已经可以不做贡献了
stack = stack[:len(stack)-1]
}
//维护答案
if len(stack) > 0 {
mp[x] = stack[len(stack)-1]
}else{
mp[x] = -1
}
//入栈
stack = append(stack,x)
}
ans := make([]int,0,len(nums1))
for _,num := range nums1 {
ans = append(ans,mp[num])
}
return ans
}func nextGreaterElement(nums1 []int, nums2 []int) []int {
/*
如果是正序遍历的话，需要维护一个单调递增的栈 但是更新答案的时候要注意下怎么更新
出栈元素的下一个最大元素就是当前要入栈的元素
*/
var stack []int
mp := make(map[int]int,len(nums2))
for i := 0 ; i < len(nums2); i ++ {
x := nums2[i]
//先出栈
for len(stack) > 0 && x >= stack[len(stack)-1] {
mp[stack[len(stack)-1]] = x
stack = stack[:len(stack)-1]
}
//入栈
stack = append(stack,x)
}
ans := make([]int,0,len(nums1))
for _,num := range nums1 {
val,ok := mp[num]
if !ok {
val = -1
}
ans = append(ans,val)
}
return ans
}739. 每日温度 - 力扣（LeetCode）
和上个题基本一样，注意是严格递增
func dailyTemperatures(temperatures []int) []int {
/*
如果是正序遍历的话，需要维护一个单调递增的栈 但是更新答案的时候要注意下怎么更新
*/
var stack []int
n := len(temperatures)
ans := make([]int,n)
for i := 0; i < n; i ++ {
x := temperatures[i]
for len(stack) > 0 && x > temperatures[stack[len(stack)-1]] {
ans[stack[len(stack)-1]] = i - stack[len(stack)-1]
stack = stack[:len(stack)-1]
}
//入栈
stack = append(stack,i)
}
return ans
}评论 (0)
