problem0895

package
v0.0.0-...-db5e768 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jul 25, 2019 License: MIT Imports: 1 Imported by: 0

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

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

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)

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL