|
1 | 1 | classFreqStack { |
2 | | -Map<Integer,Integer>map; |
3 | | -Map<Integer,Stack<Integer>>freqMap; |
4 | | -intmaxFreq; |
5 | | -publicFreqStack() { |
6 | | -freqMap =newHashMap<>(); |
7 | | -map =newHashMap<>(); |
8 | | -maxFreq =Integer.MIN_VALUE; |
9 | | - } |
10 | | - |
11 | | -publicvoidpush(intx) { |
12 | | -map.put(x,map.getOrDefault(x,0) +1); |
13 | | -maxFreq =Math.max(maxFreq,map.get(x)); |
14 | | -freqMap.computeIfAbsent(map.get(x),k ->newStack<>()).push(x); |
15 | | - } |
| 2 | +Map<Integer,Integer>valueToCurrentFrequency; |
| 3 | +Map<Integer,Stack<Integer>>frequencyToValues; |
| 4 | +intmaxFrequency; |
| 5 | +publicFreqStack() { |
| 6 | +valueToCurrentFrequency =newHashMap<>(); |
| 7 | +frequencyToValues =newHashMap<>(); |
| 8 | +maxFrequency =1; |
| 9 | + } |
16 | 10 |
|
17 | | -publicintpop() { |
18 | | -intpopped =freqMap.get(maxFreq).pop(); |
19 | | -map.put(popped,map.get(popped) -1); |
20 | | -if (freqMap.get(maxFreq).size() ==0) { |
21 | | -maxFreq--; |
22 | | - } |
| 11 | +publicvoidpush(intx) { |
| 12 | +valueToCurrentFrequency.put(x,valueToCurrentFrequency.getOrDefault(x,0) +1); |
| 13 | +frequencyToValues.computeIfAbsent(valueToCurrentFrequency.get(x),k ->newStack<>()).add(x); |
| 14 | +maxFrequency =Math.max(maxFrequency,valueToCurrentFrequency.get(x)); |
| 15 | + } |
23 | 16 |
|
24 | | -returnpopped; |
| 17 | +publicintpop() { |
| 18 | +intval =frequencyToValues.get(maxFrequency).pop(); |
| 19 | +valueToCurrentFrequency.put(val,valueToCurrentFrequency.getOrDefault(val,0) -1); |
| 20 | +if (frequencyToValues.get(maxFrequency).isEmpty()) { |
| 21 | +maxFrequency--; |
25 | 22 | } |
| 23 | +returnval; |
| 24 | + } |
26 | 25 | } |
| 26 | + |
| 27 | +/** |
| 28 | + * Your FreqStack object will be instantiated and called as such: |
| 29 | + * FreqStack obj = new FreqStack(); |
| 30 | + * obj.push(x); |
| 31 | + * int param_2 = obj.pop(); |
| 32 | + */ |