895. Maximum Frequency Stack Hard

1/**
2 * [895] Maximum Frequency Stack
3 *
4 * Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.
5 * Implement the FreqStack class:
6 * 
7 * 	FreqStack() constructs an empty frequency stack.
8 * 	void push(int val) pushes an integer val onto the top of the stack.
9 * 	int pop() removes and returns the most frequent element in the stack.
10 * 	
11 * 		If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.
12 * 	
13 * 	
14 * 
15 *  
16 * Example 1:
17 * 
18 * Input
19 * ["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
20 * [[], [5], [7], [5], [7], [4], [5], [], [], [], []]
21 * Output
22 * [null, null, null, null, null, null, null, 5, 7, 5, 4]
23 * Explanation
24 * FreqStack freqStack = new FreqStack();
25 * freqStack.push(5); // The stack is [5]
26 * freqStack.push(7); // The stack is [5,7]
27 * freqStack.push(5); // The stack is [5,7,5]
28 * freqStack.push(7); // The stack is [5,7,5,7]
29 * freqStack.push(4); // The stack is [5,7,5,7,4]
30 * freqStack.push(5); // The stack is [5,7,5,7,4,5]
31 * freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4].
32 * freqStack.pop();   // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4].
33 * freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,4].
34 * freqStack.pop();   // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].
35 * 
36 *  
37 * Constraints:
38 * 
39 * 	0 <= val <= 10^9
40 * 	At most 2 * 10^4 calls will be made to push and pop.
41 * 	It is guaranteed that there will be at least one element in the stack before calling pop.
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/maximum-frequency-stack/
47// discuss: https://leetcode.com/problems/maximum-frequency-stack/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51struct FreqStack {
52        vec![]
53    }
54
55
56/** 
57 * `&self` means the method takes an immutable reference.
58 * If you need a mutable reference, change it to `&mut self` instead.
59 */
60impl FreqStack {
61
62    fn new() -> Self {
63        
64    }
65    
66    fn push(&self, val: i32) {
67        
68    }
69    
70    fn pop(&self) -> i32 {
71        
72    }
73}
74
75/**
76 * Your FreqStack object will be instantiated and called as such:
77 * let obj = FreqStack::new();
78 * obj.push(val);
79 * let ret_2: i32 = obj.pop();
80 */
81
82// submission codes end
83
84#[cfg(test)]
85mod tests {
86    use super::*;
87
88    #[test]
89    fn test_895() {
90    }
91}
92