Week 13 @ 2025 算法周记【栈】
By Bryan
3 min
栈
LC 71. Simplify Path 简化路径
https://leetcode.com/problems/simplify-path/description/
func simplifyPath(path string) string {
splits := strings.Split(path, "/")
paths := make([]string, 0, len(splits))
for _, p:= range splits {
if p == "" || p == "." {
continue
}
if p == ".." {
if len(paths) > 0 {
paths = paths[:len(paths)-1]
}
continue
}
paths = append(paths, p)
}
return "/" + strings.Join(paths, "/")
}LC 143. Reorder List 重排链表
https://leetcode.com/problems/reorder-list/description/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reorderList(head *ListNode) {
stack := make([]*ListNode, 0, 5_0000)
for node := head; node != nil; node = node.Next {
stack = append(stack, node)
}
h := head
for {
last := pop(&stack)
next := h.Next
if last == next || last.Next == next {
last.Next = nil
break
}
h.Next = last
last.Next = next
h = next
}
}
func pop(stack *[]*ListNode) *ListNode {
l := len(*stack)
last := (*stack)[l-1]
*stack = (*stack)[:l-1]
return last
}LC 20. Valid Parentheses 有效的括号
https://leetcode.com/problems/valid-parentheses/description/
fun
c isValid(s string) bool {
pp := make([]byte, 0, len(s))
for i := range s {
c := s[i]
switch c {
case '(', '[', '{':
pp = append(pp, c)
case ')', ']', '}':
if len(pp) == 0 {
return false
}
last := pp[len(pp)-1]
pp = pp[:len(pp)-1]
if c != getPair(last) {
return false
}
}
}
return len(pp) == 0
}
func getPair(c byte) byte {
switch c {
case '(':
return ')'
case '[':
return ']'
case '{':
return '}'
}
panic("impossible")
}LC 150. Evaluate Reverse Polish Notation 逆波兰表达式求值
https://leetcode.com/problems/evaluate-reverse-polish-notation/description/
func evalRPN(tokens []string) int {
nums := make([]int, 0, len(tokens))
for _, token := range tokens {
switch token {
case "+":
a, b := pop2(&nums)
nums = append(nums, a + b)
case "-":
a, b := pop2(&nums)
nums = append(nums, a - b)
case "*":
a, b := pop2(&nums)
nums = append(nums, a * b)
case "/":
a, b := pop2(&nums)
nums = append(nums, a / b)
default:
num, _ := strconv.Atoi(token)
nums = append(nums, num)
}
}
return nums[0]
}
func pop2(nums *[]int) (a, b int) {
l := len(*nums)
a, b = (*nums)[l-2], (*nums)[l-1]
*nums = (*nums)[:l-2]
return
}LC 225. Implement Stack using Queues 用队列实现栈
https://leetcode.com/problems/implement-stack-using-queues/description/
Pop 的时间复杂度 O(N)，其他操作的时间复杂度 O(1)
type MyStack struct {
q *list.List
topElement int
}
func Constructor() MyStack {
return MyStack {
q: list.New(),
topElement: -1,
}
}
func (this *MyStack) Push(x int) {
this.q.PushBack(x)
this.topElement = x
}
func (this *MyStack) Top() int {
return this.topElement
}
func (this *MyStack) Pop() int {
n := this.q.Len()
if n == 0 {
return -1
}
for ; n > 2; n-- {
// move front value to back
front := this.q.Front()
this.q.Remove(front)
this.q.PushBack(front.Value)
}
// now n==1 or n==2
if n == 2 {
front := this.q.Front()
frontValue := front.Value.(int)
this.q.Remove(front)
this.q.PushBack(frontValue)
this.topElement = frontValue
n--
} else {
// n == 1, reset topElement to -1
this.topElement = -1
}
// now n == 1
front := this.q.Front()
frontValue := front.Value.(int)
this.q.Remove(front)
return frontValue
}
func (this *MyStack) Empty() bool {
return this.q.Len() == 0
}
/**
* Your MyStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(x);
* param_2 := obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.Empty();
*/LC 388. Longest Absolute File Path 文件的最长绝对路径
https://leetcode.com/problems/longest-absolute-file-path/description/
func lengthLongestPath(input string) int {
lines := strings.Split(input, "\n")
levelLengths := make([]int, 1_0000)
levelLengths[0] = -1
maxLength := 0
for _, line := range lines {
level, name := cutTab(line)
currentLength := levelLengths[level] + 1 + len(name)
if strings.Contains(name, ".") {
maxLength = max(maxLength, currentLength)
}
levelLengths[level+1] = currentLength
}
return maxLength
}
func cutTab(line string) (count int, trimmed string) {
for i := range line {
if line[i] != '\t' {
count = i
break
}
}
trimmed = line[count:]
return
}LC 155. Min Stack 最小栈
https://leetcode.com/problems/min-stack/description/
type MinStack struct {
nums []int
mins []int
}
const maxValue = math.MaxInt
func Constructor() MinStack {
return MinStack{
nums: []int{maxValue},
mins: []int{maxValue},
}
}
func (this *MinStack) Push(val int) {
this.nums = append(this.nums, val)
if lastValue(this.mins) >= val {
this.mins = append(this.mins, val)
}
}
func (this *MinStack) Pop() {
v := this.nums[len(this.nums)-1]
this.nums = this.nums[:len(this.nums)-1]
if v == lastValue(this.mins) {
this.mins = this.mins[:len(this.mins)-1]
}
}
func (this *MinStack) Top() int {
return lastValue(this.nums)
}
func (this *MinStack) GetMin() int {
return lastValue(this.mins)
}
func lastValue(arr []int) int {
return arr[len(arr)-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();
*/, multiple selections available,