895. Maximum Frequency Stack

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

FreqStack has two functions:

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
  • 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.

解法： 

关键是想到用HashMap of Stacks的数据结构。

e.g. 

["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]

数据结构：
stackMap: <freq, 这个freq的stack> 注意同一个数如果多次加会在多个freq的slot里出现
3: [5]
2: [5] [7]
1:  [5] [7] [4]

freqMap: <数，freq>
5: 3
7: 2
4: 1

 1 class FreqStack {
 2     HashMap<Integer, Integer> freqMap;
 3     HashMap<Integer, Stack<Integer>> stackMap;
 4     int maxFreq;
 5     public FreqStack() {
 6         freqMap = new HashMap<Integer, Integer>();
 7         stackMap = new HashMap<Integer, Stack<Integer>>();
 8         maxFreq = 0;
 9     }
10     
11     public void push(int x) {
12         int newFreq = 1;
13         if (freqMap.containsKey(x)) {
14             newFreq = freqMap.get(x) + 1;
15         }
16         freqMap.put(x, newFreq);
17         if (!stackMap.containsKey(newFreq)) {
18             stackMap.put(newFreq, new Stack<Integer>()); 
19         }
20         stackMap.get(newFreq).push(x);
21         maxFreq = Math.max(maxFreq, newFreq);
22         
23     }
24     
25     public int pop() {
26         if (maxFreq == 0) {
27             return -1;
28         }
29         
30         Integer toRemove = stackMap.get(maxFreq).pop();
31         int originalFreq = maxFreq; // maxFreq might be decreased, so keep an originalFreq to use
32         
33         if (stackMap.get(maxFreq).isEmpty()) {
34             stackMap.remove(maxFreq);
35             maxFreq--;
36         }
37         
38         if (originalFreq != 1) {
39             freqMap.put(toRemove, originalFreq - 1);
40         } else {
41             freqMap.remove(toRemove);
42         }
43         
44         return toRemove;
45     }
46 }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄