每日一道算法题036 最小栈

题目

leetCode 第 155 题，
关联类型：栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
 

示例:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.
 

提示：

pop、top 和 getMin 操作总是在 非空栈 上调用。
复制代码

做题时间

class MinStack {
    /**
     * initialize your data structure here.
     */
    public MinStack() {
        
    }

    public void push(int val) {
        
    }

    public void pop() {
        
    }

    public int top() {
       
    }

    public int getMin() {
       
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

复制代码

以上给出方法输入参数，完成作答。

题目分析

1. 想法是使用 List 实现题目要求
2. 使用一个 List 用于存储数据，一个 int 值用于保存最小值
3. 每次 push 及 pop 的时候更新最小值

解答分析

本文只分析本人做题思路，仅供参考，了解一种解题思想，其他各种做题思路请上网查阅。

解答成功:
执行耗时:6 ms,击败了97.24% 的Java用户
内存消耗:40.3 MB,击败了27.28% 的Java用户

import java.util.ArrayList;

//leetcode submit region begin(Prohibit modification and deletion)
class MinStack {
    int minNum;
    List<Integer> mList;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        mList = new ArrayList<>();
    }

    public void push(int val) {
        if (mList.size() == 0) {
            minNum = val;
        } else {
            minNum = val < minNum ? val : minNum;
        }
        mList.add(val);
    }

    public void pop() {
        if (mList.get(mList.size() - 1) == minNum && mList.size() > 1) {
            mList.remove(mList.size() - 1);
            minNum = mList.get(0);
            for (int i = 0; i < mList.size(); i++) {
                minNum = mList.get(i) < minNum ? mList.get(i) : minNum;
            }
        } else {
            mList.remove(mList.size() - 1);
        }
    }

    public int top() {
       return mList.get(mList.size() - 1);
    }

    public int getMin() {
        return minNum;
    }
}
复制代码