首页 > itarticle > min stack

min stack

admin 1月 30, 2021 0

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
getMin() – Retrieve the minimum element in the stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
class  {
private ArrayList<Integer> st=new ArrayList<>();
    private ArrayList<Integer> minst=new ArrayList<>();
    
    public void push(int x) {
        st.add(x);
        if(minst.isEmpty()||minst.get(minst.size()-1)>=x)
            minst.add(x);
    }
    
    public void pop() {
        if(st.isEmpty())
            return;
        int element=st.remove(st.size()-1);
        if(!minst.isEmpty()&& element==minst.get(minst.size()-1))
        {
            minst.remove(minst.size()-1);
        }
    }
    
    public int top() {
        if(!st.isEmpty())
            return st.get(st.size()-1);
        return 0;
    }
    
    public int getMin() {
        if(!minst.isEmpty())
        return minst.get(minst.size()-1);
        return 0;
    }
}

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能