最大栈
洪笳淏 Lv4
 2021-10-03 15:16:00      

最大栈介绍

  直接参考Leetcode上895题：895. 最大频率栈

实现 FreqStack，模拟类似栈的数据结构的操作的一个类。

FreqStack 有两个函数：

  • push(int x)，将整数 x 推入栈中。
  • pop()，它移除并返回栈中出现最频繁的元素。
    • 如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
输入：
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
输出：[null,null,null,null,null,null,null,5,7,5,4]
解释：
执行六次 .push 操作后，栈自底向上为 [5,7,5,7,4,5]。然后：

pop() -> 返回 5，因为 5 是出现频率最高的。
栈变成 [5,7,5,7,4]。

pop() -> 返回 7，因为 5 和 7 都是频率最高的，但 7 最接近栈顶。
栈变成 [5,7,5,4]。

pop() -> 返回 5 。
栈变成 [5,7,4]。

pop() -> 返回 4 。
栈变成 [5,7]。

提示：

  • 对 FreqStack.push(int x) 的调用中 0 <= x <= 10^9。
  • 如果栈的元素数目为零，则保证不会调用 FreqStack.pop()。
  • 单个测试样例中，对 FreqStack.push 的总调用次数不会超过 10000。
  • 单个测试样例中，对 FreqStack.pop 的总调用次数不会超过 10000。
  • 所有测试样例中，对 FreqStack.push 和 FreqStack.pop 的总调用次数不会超过 150000。

问题分析

  这种设计数据结构的问题，主要是要搞清楚问题的难点在哪里，然后结合各种基本数据结构的特性，高效实现题目要求的 API。

那么，我们仔细思考一下 push 和 pop 方法，难点如下：

1、每次 pop 时，必须要知道频率最高的元素是什么。

2、如果频率最高的元素有多个，还得知道哪个是最近 push 进来的元素是哪个。

为了实现上述难点，我们要做到以下几点：

1、肯定要有一个变量 maxFreq 记录当前栈中最高的频率是多少。

2、我们得知道一个频率 freq 对应的元素有哪些，且这些元素要有时间顺序。

3、随着 pop 的调用，每个 val 对应的频率会变化，所以还得维持一个映射记录每个 val 对应的 freq。

设计实现

  综上，我们可以先实现 FreqStack 所需的数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
type FreqStack struct {
    maxFreq     int     // 出现最大频数的记录
    valToFreq   map[int]int
    freqToVal   map[int]*stack
}

func Constructor() FreqStack {	// 初始化最大栈
    mf := 0
    vf := make(map[int]int,0)
    fv := make(map[int]*stack,0)
    return FreqStack{
        maxFreq     :       mf,
        valToFreq   :       vf,
        freqToVal   :       fv,
    }
}

  我们来亲自构建stack这一数据结构及其方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
type stack struct {			// 栈可以用一个简单的切片来表示
    list        []int
}

func constructorStack() *stack {	// 初始化栈
    l := make([]int,0)
    return &stack{
        list    :       l,   
    }
}

func (s *stack) push(val int) {		// 入栈方法
    s.list = append(s.list,val)
}

func (s *stack) pop() int {		// 出栈方法，返回出栈的元素
    n := len(s.list)
    old := s.list
    last := old[n-1]
    if n == 1 {
        s.list = []int{}
    } else {
        s.list = old[:n-1]
    }
    return last
}

func (s *stack) len() int {		// 计算栈的容量的方法
    n := len(s.list)
    return n
}

  其实这有点类似前文LFU算法，注意 freqToVal 中 val 列表用一个栈实现，如果一个 freq 对应的元素有多个，根据栈的特点，可以首先取出最近添加的元素。

要记住在 push 和 pop 方法中同时修改 maxFreq、VF 表、FV 表，否则容易出现 bug。

Push方法

现在，我们可以来实现 push 方法了。

我们要分别实现对FreqStack结构体中三个元素的更新。

  • valToFreq(VF表)：如果val对应的映射存在，则映射到的值加1；如果不存在，则初始为1；
  • freqToVal(FV表)：如果新加入的val对应的新的freq在FV表中没有初始化的栈，则创建一个新栈，将该val入栈；否则直接入栈；
  • maxFreq：比较新的freq与原始的maxFreq，取大者作为maxFreq。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func (this *FreqStack) Push(val int)  {
    var freq int

    // 修改vf表
    if _,ok := this.valToFreq[val]; !ok {
        this.valToFreq[val] = 1
    } else {
        this.valToFreq[val]++
    }
    freq = this.valToFreq[val]

    // 修改fv表
    if _,ok := this.freqToVal[freq]; !ok {
        this.freqToVal[freq] = constructorStack()
        this.freqToVal[freq].push(val)
    } else {
        this.freqToVal[freq].push(val)
    }

    // 修改最大频数
    if freq > this.maxFreq {
        this.maxFreq = freq
    }
}

Pop()方法

我们要分别实现对FreqStack结构体中三个元素的更新。

  • freqToVal(FV表)：找到maxFreq在FV表中的映射，如果映射到的stack容量为1(说明只有一个数的频率是maxFreq)，则将maxFreq减一并将栈顶元素出栈；否则直接将栈顶元素出栈；
  • valToFreq(VF表)：找到出栈元素对应的VF表的映射（代表其出现频率），将其直接减一；
  • maxFreq：已经在修改FV表时进行了选择性的修改，不做特殊操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func (this *FreqStack) Pop() int {
    if this.maxFreq == 0 {
        return 0
    }

    var popNum int

    // 修改fv表
    freq := this.maxFreq
    if this.freqToVal[freq].len() == 1 {
        popNum = this.freqToVal[freq].pop()
        this.maxFreq--      // 修改最大频数
    } else {
        popNum = this.freqToVal[freq].pop() 
    }

    // 修改vf表
    this.valToFreq[popNum]--
    return popNum
}

总结

完整的最大栈实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
type stack struct {
    list        []int
}

func (s *stack) push(val int) {
    s.list = append(s.list,val)
}

func (s *stack) pop() int {
    n := len(s.list)
    old := s.list
    last := old[n-1]
    if n == 1 {
        s.list = []int{}
    } else {
        s.list = old[:n-1]
    }
    return last
}

func (s *stack) len() int {
    n := len(s.list)
    return n
}

func constructorStack() *stack {
    l := make([]int,0)
    return &stack{
        list    :       l,   
    }
}

type FreqStack struct {
    maxFreq     int     // 出现最大频数的记录
    valToFreq   map[int]int
    freqToVal   map[int]*stack
}


func Constructor() FreqStack {
    mf := 0
    vf := make(map[int]int,0)
    fv := make(map[int]*stack,0)
    return FreqStack{
        maxFreq     :       mf,
        valToFreq   :       vf,
        freqToVal   :       fv,
    }
}


func (this *FreqStack) Push(val int)  {
    var freq int

    // 修改vf表
    if _,ok := this.valToFreq[val]; !ok {
        this.valToFreq[val] = 1
    } else {
        this.valToFreq[val]++
    }
    freq = this.valToFreq[val]

    // 修改fv表
    if _,ok := this.freqToVal[freq]; !ok {
        this.freqToVal[freq] = constructorStack()
        this.freqToVal[freq].push(val)
    } else {
        this.freqToVal[freq].push(val)
    }

    // 修改最大频数
    if freq > this.maxFreq {
        this.maxFreq = freq
    }
}


func (this *FreqStack) Pop() int {
    if this.maxFreq == 0 {
        return 0
    }

    var popNum int

    // 修改fv表
    freq := this.maxFreq
    if this.freqToVal[freq].len() == 1 {
        popNum = this.freqToVal[freq].pop()
        this.maxFreq--      // 修改最大频数
    } else {
        popNum = this.freqToVal[freq].pop() 
    }

    // 修改vf表
    this.valToFreq[popNum]--
    return popNum
}


/**
 * Your FreqStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(val);
 * param_2 := obj.Pop();
 */
  • Post title：最大栈
  • Post author：洪笳淏
  • Create time：2021-10-03 15:16:00
  • Post link：https://jiahaohong1997.github.io/2021/10/03/最大栈/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments