题解 | #最大体重的牛#

考察知识点：栈

解题思路：使用两个栈，一个栈存储数据，一个栈存储当前栈的最大值，入栈时检查新入栈的值是否比最大值栈栈顶元素要大，并且把两者中较大的元素入最大值栈。出栈时两个栈同时出栈，这样就保证了每次从最大值栈获取到的元素都是数据栈中的最大值。时间复杂度O(1)，空间复杂度O(N)

吐槽下牛客新的题库，这道题在力扣应该类模板已经有了，直接把每个方法填好就行，这题搞得要自己去遍历操作数组来判断当前的操作，太费劲了，浪费太多时间在题目之外的代码

import java.util.*;

class MaxStack {
    Stack<Integer> data;
    Stack<Integer> max;

    public void init() {
        data = new Stack<>();
        max = new Stack<>(); 
    }

    public void push(int e) {
        data.push(e);
        int m = e;
        if (!max.isEmpty()) {
            m = Math.max(max.peek(), e);   
        }
        max.push(m);
    }

    public void pop() {
        data.pop();
        max.pop();
    }

    public int top() {
        return data.peek();
    }

    public int getMax() {
        return max.peek();
    }

}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param op string字符串一维数组 
     * @param vals int整型二维数组 
     * @return int整型一维数组
     */
    public int[] max_weight_cow (String[] op, int[][] vals) {
        // write code here
        MaxStack ms = new MaxStack();
        int[] res = new int[vals.length];
        
        for (int i = 0; i < op.length; i ++) {
            String o = op[i];
            switch (o) {
            case "MaxCowStack":
                ms.init();
                res[i] = -1;
                break;
            case "push":
                ms.push(vals[i][1]);
                res[i] = -1;
                break;
            case "pop":
                ms.pop();
                res[i] = -1;
                break;
            case "top":
                res[i] = ms.top();
                break;
            case "getMax":
                res[i] = ms.getMax();
                break;
            }
        }
        return res;
    }
}