1.栈的定义:
栈(Stack)又名堆栈,它是一种重要的数据结构。从数据结构角度看,栈也是线性表,其特殊性在于栈的基本操作是线性表操作的子集,它是操作受限的线性表,因此,可称为限定性的数据结构。限定它仅在表尾进行插入或删除操作。表尾称为栈顶,相应地,表头称为栈底。栈的基本操作除了在栈顶进行插入和删除外,还有栈的初始化,判空以及取栈顶元素等。
2.栈的常用算法例子
例子1: leet-code:20 有效的括号:
题目描述:给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。示例 1:输入: "()"输出: true示例 2:输入: "()[]{}"输出: true示例 3:输入: "(]"输出: false示例 4:输入: "([)]"输出: false示例 5:输入: "{[]}"输出: true
解题思路:
通过分析题目要求我们可以看出,这是一个对称字符串的匹配问题,对于这种问题需要将没有匹配到的字符一直保存着,直到没有字符串比较为止,而这正好就是栈所做的事情,所以我们的首选是栈,思路如下:
-1.先初步过滤掉数据,将奇数的字符串丢掉,这一步用来删选明显不成功的那些字符串组合。
-2.遍历字符串,将左括号(,[,{入栈。
-3.右括号到来的时候,去栈中取栈顶数据比较,是匹配的字符就出栈(备注:考虑栈为空的时候)
-4.都处理完了,栈非空为false,否则为true
代码实现:
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}
运行结果:
例子2:简化路径:
题目描述:leet-code71以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。更多信息请参阅:Linux / Unix中的绝对路径 vs 相对路径请注意,返回的规范路径必须始终以斜杠 / 开头,并且两个目录名之间必须只有一个斜杠 /。最后一个目录名(如果存在)不能以 / 结尾。此外,规范路径必须是表示绝对路径的最短字符串。示例 1:输入:"/home/"输出:"/home"解释:注意,最后一个目录名后面没有斜杠。示例 2:输入:"/../"输出:"/"解释:从根目录向上一级是不可行的,因为根是你可以到达的最高级。示例 3:输入:"/home//foo/"输出:"/home/foo"解释:在规范路径中,多个连续斜杠需要用一个斜杠替换。示例 4:输入:"/a/./b/../../c/"输出:"/c"示例 5:输入:"/a/../../b/../c//.//"输出:"/c"示例 6:输入:"/a//b////c/d//././/.."输出:"/a/b/c"
解题思路:
分析题目我们可以看出,后面的字符串的处理逻辑需要依赖与前面存储的字符串特性,而这个正好符合栈的特性,所以我们通过栈来解决这个问题,如下所示:
-1.先将字符串转换成字符串数组,通过分隔符/,这里注意Go的strings.Split()会把//、///这种连续的字符 生成空字符串""来存储,所以我们需要过滤掉这些""字符串。
-2.对于路径来说只剩下..和.这两种特殊的字符,需要单独处理,..的话,需要将栈中的数据出栈,.字符的话不需要入栈,这两种之外的都需要做入栈操作。如此以来栈中存储的就是有效的路径字符串了。
-3.我们将栈中的字符串通过/拼接起来就是所需要的路径了,不过记得最后一位不要添加/
代码:
func simplifyPath(path string) string { tmps := strings.Split(path,"/") var paths []string for _,s:=range tmps { if len(s) != 0{ paths = append(paths,s) } } // fmt.Println("name",paths) var stacks []string for i:=0;i<len(paths);i++{ if paths[i]==".." { if len(stacks) > 0{ // 防止首路径就是..,例如../ stacks=stacks[:len(stacks)-1] } continue } if paths[i]!="."{ stacks=append(stacks,paths[i]) } } // fmt.Println("name",stacks,len(stacks)) resStr :="" for idx,s:=range stacks { resStr += s if idx != len(stacks)-1{ // 路径末尾不加/ resStr += "/" } } return "/"+resStr // 路径头部加上/}
输出结果:
例子3: leet-code42:接雨水
题目描述:
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。感谢 Marcos 贡献此图。示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6
解题思路:
通过分析题目中的图,我们可以看出,接雨水是从当中的最高点往左右两边流的,而左右两边是对称的,所用算法相同,所以该问题变成了拆分数组,计算两边的数据结果,然后合并数组的操作。
计算数组的结果,后面的雨水的多少依赖于前面的柱子高度,这样一来,就需要用到栈来操作了。
-1.拆分数组,找到数组中的最高点,分成左边和右边两个数组。
-2.计算左边数组的结果。
--2.1.高1<高2:从左往右,第一个高的入栈,后续比他小或等于的计算数值,求和;
--2.2.高1==高2:从左往右,算法同1
--2.3.高1=0: 不入栈,不做计算;// 最左边
-3.按照2的方法计算右边数组的结果。
-4.合并左右两边的计算结果。
代码:
func trap(height []int) int { top := getTopIndx(height)
all := sum(height[:top]) // 计算左边的数据和 if top < len(height) { var tmp []int for i:= len(height)-1; i>top; i--{ tmp = append(tmp,height[i]) } all += sum(tmp) // 计算右边的数据和 } return all // 左右数据合并}
func getTopIndx(height []int) int { if len(height) == 0 { return 0 } var idx int var stacks []int // 这里的栈只是用来记录数组中的最大值 for i:=0;i<len(height);i++{ if i== 0{ // 首元素存入栈中 stacks = append(stacks,height[i]) }
if height[i] > stacks[len(stacks)-1] { // 与栈顶元素比较,将数据高的存储到栈顶 idx = i stacks = append(stacks,height[i]) } } return idx}func sum(height []int) int { if len(height) == 0 { return 0 } var stacks []int var h, s int for i:=0;i<len(height);i++ { if i == 0 { stacks = append(stacks,height[i]) } if len(stacks) > 0 { h = stacks[len(stacks)-1] } if height[i] > h { // 出栈再入栈 stacks[len(stacks)-1] = height[i] } else { s += h - height[i] } }
return s}
运行结果:
例子4: leet-code:59.滑动窗口的最大值
题目描述:给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。示例:输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3输出: [3,3,5,5,6,7]解释:滑动窗口的位置 最大值--------------- -----[1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7
解题思路:
这个题目比较简单,主要切分成两个问题,一个是循环找m个k的数据;一个是计算k个元素的最大值。
第k个元素最大值可以利用栈来计算。
代码:
func maxSlidingWindow(nums []int, k int) []int { if len(nums) < k { return nil } var res []int for i:=0;i<len(nums)-k+1;i++ { max,ok := maxData(nums[i:i+k],k) if ok { res = append(res,max) } } return res}func maxData(nums []int,k int) (max int, ok bool) { if len(nums) != k || len(nums) == 0{ return } var stacks []int // 用栈来存储最大值 stacks = append(stacks,nums[0]) for idx, num := range nums { for i := len(stacks)-1; i>=0; i--{ if num > stacks[i] { stacks = stacks[:i] continue } } if idx != 0 { stacks = append(stacks,num) } } max = stacks[0] return max, true}