剑指offer刷题 - day06

JZ29 用两个栈实现队列

这道题看着扑朔迷离，按着官方的题解来的，这删除时间复杂度是 O(n)

package main

import "fmt"

var stack1 []int
var stack2 []int

func Push(node int) {
    stack1 = append(stack1, node)
}

func Pop() int {
    stack2 = []int{}
    for len(stack1) != 0 {
        stack2 = append(stack2, stack1[len(stack1)-1])
        stack1 = stack1[:len(stack1)-1]
    }
    v := stack2[len(stack2)-1]
    stack2 = stack2[:len(stack2)-1]
    stack1 = []int{}
    for len(stack2) != 0 {
        stack1 = append(stack1, stack2[len(stack2)-1])
        stack2 = stack2[:len(stack2)-1]
    }
    return v
}

func main() {
    Push(1)
    Push(2)
    fmt.Println(Pop())
    fmt.Println(Pop())
}

JZ30 包含min函数的栈

思路

栈操作简单，关键难点在取最小值，很巧妙的一个办法，假设第一个入栈元素最小，然后入栈一个，和前面的最小值比较，用单独的一个栈存储这个最小值，形成如此的关系：min(min(min(a,b),c),d)

这是官方提供的图示：

代码

package main

import "fmt"

type DataType = int
type Node struct {
    Data DataType
    Next *Node
}
type Stack struct {
    Head *Node
}

func NewStack() *Stack {
    stack := new(Stack)
    stack.Head = &Node{}
    return stack
}

func (s *Stack) Push(d DataType) {
    newNode := &Node{Data: d}
    newNode.Next = s.Head.Next
    s.Head.Next = newNode
}
func (s *Stack) Pop() DataType {
    if s.Head.Next == nil {
        panic(nil)
    }
    node := s.Head.Next
    s.Head.Next = node.Next
    return node.Data
}
func (s *Stack) Top() DataType {
    if s.Head.Next == nil {
        panic(nil)
    }
    return s.Head.Next.Data
}
func (s *Stack) Empty() bool {
    return s.Head.Next == nil
}

var stack = NewStack()
var seqStack = NewStack()

func Push(node int) {
    stack.Push(node)
    if seqStack.Empty() {
        seqStack.Push(node)
    } else {
        min := seqStack.Top()
        if node < min {
            seqStack.Push(node)
        } else {
            seqStack.Push(min)
        }
    }
}
func Pop() {
    stack.Pop()
    seqStack.Pop()
}
func Top() int {
    return stack.Top()
}
func Min() int {
    return seqStack.Top()
}

func main() {
    Push(-1)
    Push(2)
    fmt.Println(Min())
    fmt.Println(Top())
    Pop()
    Push(-1)
    fmt.Println(Top())
    fmt.Println(Min())
}