problem0895

README

895. Maximum Frequency Stack

题目

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack`has two functions:

• push(int x), which pushes an integer x onto the stack.
• pop(), which removes and returns the most frequent element in the stack.
  • If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

Example 1:

Input:
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
Output: [null,null,null,null,null,null,null,5,7,5,4]
Explanation:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top.  Then:

pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].

pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].

pop() -> returns 5.
The stack becomes [5,7,4].

pop() -> returns 4.
The stack becomes [5,7].

Note:

• Calls to FreqStack.push(int x)`will be such that 0 <= x <= 10^9.
• It is guaranteed that FreqStack.pop() won't be called if the stack has zero elements.
• The total number of FreqStack.push calls will not exceed 10000 in a single test case.
• The total number of FreqStack.pop`calls will not exceed 10000 in a single test case.
• The total number of FreqStack.push and FreqStack.pop calls will not exceed 150000 across all test cases.

解题思路

见程序注释

Documentation

Index

• type FreqStack
  • func Constructor() FreqStack
  • func (fs *FreqStack) Pop() int
  • func (fs *FreqStack) Push(x int)
• type PQ
  • func (pq PQ) Len() int
  • func (pq PQ) Less(i, j int) bool
  • func (pq *PQ) Pop() interface{}
  • func (pq *PQ) Push(x interface{})
  • func (pq PQ) Swap(i, j int)

Types

type FreqStack

type FreqStack struct {
	// contains filtered or unexported fields
}

FreqStack object will be instantiated and called as such: obj := Constructor(); obj.Push(x); param_2 := obj.Pop();

func Constructor

func Constructor() FreqStack

Constructor 构建 FreqStack

func (*FreqStack) Pop

func (fs *FreqStack) Pop() int

Pop 从 fs 中弹出元素

func (*FreqStack) Push

func (fs *FreqStack) Push(x int)

Push 在 fs 中放入 x

type PQ

type PQ []*entry

PQ implements heap.Interface and holds entries.

func (PQ) Len

func (pq PQ) Len() int

func (PQ) Less

func (pq PQ) Less(i, j int) bool

func (*PQ) Pop

func (pq *PQ) Pop() interface{}

Pop 从 pq 中取出最优先的 entry

func (*PQ) Push

func (pq *PQ) Push(x interface{})

Push 往 pq 中放 entry

func (PQ) Swap

func (pq PQ) Swap(i, j int)