LC.155. Min Stack(优化，针对整块一样数传入)

如果有特别多重复的数进来的情况，并且是一整块一样的数进来，那是可以被优化的。

1111111 222222 -1-1-1-1 111111 -2-2-2-2-2 33333

如果进来的数字是交叉的，则优化空间有限: 1212121212

 1 public class LC_155_MinStack_II {
 2 
 3     private Deque<Integer> stack ;
 4     private Deque<Integer> minStack ;
 5     //keep each minStack item's times
 6     private Deque<Integer> counter ;
 7 
 8     /** initialize your data structure here. */
 9     public LC_155_MinStack_II() {
10         stack = new LinkedList<>() ;
11         minStack = new LinkedList<>();
12         counter = new LinkedList<>();
13     }
14     /*
15      stack      -2  -2 -2  0  0  -3
16      min        -2 -3
17      counter    5   1
18     * */
19     public void push(int x) {
20         stack.push(x);
21         if (minStack.isEmpty()){
22             minStack.push(x);
23             counter.push(1); //initialize new item
24         } else{
25             if (minStack.peek() < x){
26                 int times = counter.pop();
27                 counter.push(times+1);
28             } else{
29                 minStack.push(x);
30                 counter.push(1);
31             }
32         }
33     }
34     /*
35         stack      -2  -2 -2  0  0  -3
36         min        -2  -3
37         counter    5   1
38        * */
39     public void pop() {
40         if (stack.isEmpty()) return ;
41         stack.pop();
42         //handle the min: only pop minStack when the counter's item reach 0
43         int times = counter.pop();
44         if (times>1){
45             times--;
46             counter.push(times);
47         }
48         //when counter == 1 or less(shouldnt possible be <0), then directly pop counter
49         else {
50             minStack.pop();
51         }
52     }
53     //peek
54     public int top() {
55         if (stack.isEmpty()) return -1 ;
56         return stack.peek() ;
57     }
58 
59     public int getMin() {
60         if (minStack.isEmpty()) return -1 ;
61         return minStack.peek();
62     }
63 }