『代码随想录』栈与队列（Stack & Queue）

DAY 10

232.用栈实现队列

因为栈和队列的出队顺序是反的，所以再来个栈倒腾一下就是正的了

type MyQueue struct {
    in  []int
    out []int
}

func Constructor() MyQueue {
    return MyQueue{
        in:  []int{},
        out: []int{},
    }
}

func (this *MyQueue) Push(x int) {
    this.in = append(this.in, x)
}

func (this *MyQueue) shift() { // 倒腾一下
    for len(this.in) != 0 {
        this.out = append(this.out, this.in[len(this.in)-1])
        this.in = this.in[:len(this.in)-1]
    }
}

func (this *MyQueue) Pop() int {
    if len(this.out) == 0 {
        this.shift()
    }
    ans := this.out[len(this.out)-1]
    this.out = this.out[:len(this.out)-1]
    return ans
}

func (this *MyQueue) Peek() int {
    if len(this.out) == 0 {
        this.shift()
    }
    return this.out[len(this.out)-1]
}

func (this *MyQueue) Empty() bool {
    return len(this.in) == 0 && len(this.out) == 0
}

---

225.用队列实现栈

一个队列就够了

出栈的话，把前 n-1 个元素扔到后面去（我称之为 shift 操作），当前元素就是刚入队的元素了

Top 的话就先出栈再放进去

type MyStack struct {
    q []int
}

func Constructor() MyStack {
    return MyStack{
        q: []int{},
    }
}

func (this *MyStack) Push(x int) {
    this.q = append(this.q, x)
}

func (this *MyStack) shift() { // 将前 n-1 个元素出队再加入
    n := len(this.q)
    for i := 0; i < n-1; i++ {
        this.q = append(this.q[1:], this.q[0])
    }
}

func (this *MyStack) Pop() int {
    this.shift()
    ans := this.q[0]
    this.q = this.q[1:]
    return ans
}

func (this *MyStack) Top() int {
    ans := this.Pop()
    this.Push(ans)
    return ans
}

func (this *MyStack) Empty() bool {
    return len(this.q) == 0
}

也可以换个思路，在 Push 的时候就 shift 也行，看上去更简单

type MyStack struct {
    q []int
}

func Constructor() MyStack {
    return MyStack{
        q: []int{},
    }
}

func (this *MyStack) Push(x int) {
    this.q = append(this.q, x)
    this.shift()
}

func (this *MyStack) shift() { // 将前 n-1 个元素出队再加入
    n := len(this.q)
    for i := 0; i < n-1; i++ {
        this.q = append(this.q[1:], this.q[0])
    }
}

func (this *MyStack) Pop() int {
    ans := this.q[0]
    this.q = this.q[1:]
    return ans
}

func (this *MyStack) Top() int {
    return this.q[0]
}

func (this *MyStack) Empty() bool {
    return len(this.q) == 0
}

DAY 11

20.有效的括号

经典的栈应用

func isValid(s string) bool {
    stack := []rune{}
    for _, c := range s {
        switch c {
        case '(', '[', '{':
            stack = append(stack, c)
        case ')':
            if len(stack) == 0 || stack[len(stack)-1] != '(' {
                return false
            }
            stack = stack[:len(stack)-1]
        case ']':
            if len(stack) == 0 || stack[len(stack)-1] != '[' {
                return false
            }
            stack = stack[:len(stack)-1]
        case '}':
            if len(stack) == 0 || stack[len(stack)-1] != '{' {
                return false
            }
            stack = stack[:len(stack)-1]
        }

    }

    if len(stack) != 0 {
        return false
    }

    return true
}

---

1047.删除字符串中的所有相邻重复项

func removeDuplicates(s string) string {
    stack := []rune{}

    for _, c := range s {
        if len(stack) != 0 && c == stack[len(stack)-1] {
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, c)
        }
    }

    return string(stack)
}

---

150.逆波兰表达式求值

经典中的经典

func evalRPN(tokens []string) int {
    stack := []int{}
    for _, s := range tokens {
        n := len(stack)
        switch s {
        case "+":
            stack = append(stack[:n-2], stack[n-2]+stack[n-1])
        case "-":
            stack = append(stack[:n-2], stack[n-2]-stack[n-1])
        case "*":
            stack = append(stack[:n-2], stack[n-2]*stack[n-1])
        case "/":
            stack = append(stack[:n-2], stack[n-2]/stack[n-1])
        default:
            stack = append(stack, atoi(s))
        }
    }
    return stack[0]
}

func atoi(x string) int {
    opt, ans := 1, 0
    for _, c := range x {
        if c == '-' {
            opt = -1
            continue
        }
        ans = ans*10 + int(c-'0')
    }
    return ans * opt
}

DAY 12

周日休息

DAY 13

239.滑动窗口最大值

非常好的单调队列例题

单调队列，队列中从头到尾单调递减

• Pop：传入当前窗口移动需要弹出的值，如果等于头元素则弹出
• Push：在尾部尝试加入，如果遇到比当前元素小的都从尾部弹出
• GetMax：取头元素

type MonoQ struct {
    data []int
}

func NewMonoQ() MonoQ {
    return MonoQ{
        data: []int{},
    }
}

// Pop 传入当前窗口移动需要弹出的值，如果等于头元素则弹出
func (q *MonoQ) Pop(x int) {
    if len(q.data) != 0 && x == q.data[0] {
        q.data = q.data[1:]
    }
}

// Push 传入当前窗口移动需要压入的值，如果大于尾元素则弹出尾元素，直到小于等于尾元素
func (q *MonoQ) Push(x int) {
    for len(q.data) != 0 && x > q.data[len(q.data)-1] {
        q.data = q.data[:len(q.data)-1]
    }
    q.data = append(q.data, x)
}

// GetMax 获取当前窗口最大值
func (q *MonoQ) GetMax() int {
    return q.data[0]
}

func maxSlidingWindow(nums []int, k int) []int {
    n := len(nums)
    ans := []int{}
    q := NewMonoQ()
    for i := 0; i < k; i++ {
        q.Push(nums[i])
    }
    ans = append(ans, q.GetMax())
    for i := k; i < n; i++ {
        q.Pop(nums[i-k])
        q.Push(nums[i])
        ans = append(ans, q.GetMax())
    }
    return ans
}

---

347.前 K 个高频元素

两种方法，拿到频率的 map 之后用堆维护前 K 个，或者直接排序再取前 K 个

复习一下 Golang 里面的优先队列和排序

用惯了 C++ STL 的开箱即用的优先队列，我只能说 Golang 的优先队列真的不好用（

• 排序，记得导入 sort 包

  使用内建的 Ints

  nums := []int{4, 2, 3, 1}
  sort.Ints(nums)

  使用 sort.Slice

  sort.Slice(people, func(i, j int) bool {
      return people[i].Age < people[j].Age
  })

• 优先队列，记得导入 heap 包

  需要实现几个接口，在使用的时候，如果你是直接将一个切片转换成堆，需要使用 heap.Init

  需要注意的是使用的时候不是面向对象的，你需要使用 heap.XX 来操作

  元素仅为 int 的简单队列

  type IntPriorityQueue []int
  
  func (pq IntPriorityQueue) Len() int           { return len(pq) }
  func (pq IntPriorityQueue) Less(i, j int) bool { return pq[i] < pq[j] }
  func (pq IntPriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
  
  func (pq *IntPriorityQueue) Push(x interface{}) {
  	*pq = append(*pq, x.(int))
  }
  
  func (pq *IntPriorityQueue) Pop() interface{} {
  	old := *pq
  	n := len(old)
  	item := old[n-1]
  	*pq = old[0 : n-1]
  	return item
  }
  
  func main() {
  	pq := &IntPriorityQueue{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}
  
  	// 建立优先队列堆
  	heap.Init(pq)
  
  	// 向优先队列中添加元素
  	heap.Push(pq, 7)
  
  	// 从优先队列中按照优先级取出元素
  	for pq.Len() > 0 {
  		fmt.Printf("%d ", heap.Pop(pq))
  	}
  }

  根据结构体中的一个字段进行排序的队列

  // Item 表示优先队列中的元素
  type Item struct {
  	value    interface{} // 元素的值
  	priority int         // 优先级
  }
  
  // PriorityQueue 实现了heap.Interface接口
  type PriorityQueue []Item
  
  func (pq PriorityQueue) Len() int { return len(pq) }
  
  func (pq PriorityQueue) Less(i, j int) bool {
  	// 这里我们使用优先级来决定元素的顺序，较小的优先级排在前面
  	return pq[i].priority < pq[j].priority
  }
  
  func (pq PriorityQueue) Swap(i, j int) {
  	pq[i], pq[j] = pq[j], pq[i]
  }
  
  func (pq *PriorityQueue) Push(x interface{}) {
  	item := x.(Item)
  	*pq = append(*pq, item)
  }
  
  func (pq *PriorityQueue) Pop() interface{} {
  	old := *pq
  	n := len(old)
  	item := old[n-1]
  	*pq = old[0 : n-1]
  	return item
  }
  
  func main() {
  	// 创建一个优先队列
  	pq := make(PriorityQueue, 0)
  
  	// 添加元素到优先队列
  	heap.Push(&pq, Item{value: "B", priority: 2})
  	heap.Push(&pq, Item{value: "C", priority: 1})
  	heap.Push(&pq, Item{value: "A", priority: 3})
  
  	// 从优先队列中按照优先级取出元素
  	for pq.Len() > 0 {
  		item := heap.Pop(&pq).(Item)
  		fmt.Printf("%s (priority: %d)\n", item.value, item.priority)
  	}
  }

言归正传，本体的两种方法

• 直接排序

  func topKFrequent(nums []int, k int) []int {
      m := make(map[int]int)
  
      for _, v := range nums {
          m[v]++
      }
  
      count := make([][2]int, 0, len(m))
      for k, v := range m {
          count = append(count, [2]int{k, v})
      }
  
      sort.Slice(count, func(i, j int) bool {
          return count[i][1] > count[j][1]
      })
  
      ans := make([]int, 0, k)
  
      for i := 0; i < k; i++ {
          ans = append(ans, count[i][0])
      }
      return ans
  }

  还可以更简单

  func topKFrequent(nums []int, k int) []int {
      m := make(map[int]int)
      for _, v := range nums {
          m[v]++
      }
  
      ans := make([]int, 0, len(m))
      for k, _ := range m {
          ans = append(ans, k)
      }
  
      sort.Slice(ans, func(i, j int) bool {
          return m[ans[i]] > m[ans[j]]
      })
  
      return ans[:k]
  }

• 维护大顶堆

  type Item struct {
      value int
      freq  int
  }
  
  type PriorityQueue []Item
  
  func (pq PriorityQueue) Len() int           { return len(pq) }
  func (pq PriorityQueue) Less(i, j int) bool { return pq[i].freq < pq[j].freq }
  func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
  
  func (pq *PriorityQueue) Push(x interface{}) {
      item := x.(Item)
      *pq = append(*pq, item)
  }
  func (pq *PriorityQueue) Pop() interface{} {
      old := *pq
      n := len(old)
      item := old[n-1]
      *pq = old[0 : n-1]
      return item
  }
  
  func topKFrequent(nums []int, k int) []int {
      m := make(map[int]int)
      for _, num := range nums {
          m[num]++
      }
  
      pq := make(PriorityQueue, 0)
      for value, freq := range m {
          heap.Push(&pq, Item{value, freq})
          if pq.Len() > k {
              heap.Pop(&pq)
          }
      }
  
      ans := make([]int, k)
      for i := 0; i < k; i++ {
          item := heap.Pop(&pq).(Item)
          ans[i] = item.value
      }
  
      return ans
  }