题解 | #最大体重的牛#

知识点：栈

题目中输入的牛序号属于无用数据，只需要关注重量即可。

使用两个栈：

一个栈负责正常的操作，用于得到top的结果；

另一个栈（最大栈）负责存储当前栈中的最大值，具体来说，若最大栈中无元素，则此时最大值为当前入栈的值，若栈中有元素，则需要和栈顶的元素比较，若栈顶元素更大，则将栈顶元素再次入栈，若当前元素更大，则将当前元素入栈，保证栈顶的元素最大即可，这就可以以O(1)的时间复杂度得到最大元素。

Java题解如下：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param op string字符串一维数组 
     * @param vals int整型二维数组 
     * @return int整型一维数组
     */
    public int[] max_weight_cow (String[] op, int[][] vals) {
        // write code here
        Deque<Integer> stack = new ArrayDeque<>();
        Deque<Integer> maxStack = new ArrayDeque<>();
        int n = op.length;
        int[] ans = new int[n];
        for(int i = 0; i < n; i++) {
            ans[i] = -1;
            if(op[i].equals("MaxCowStack")) {
                stack = new ArrayDeque<>();
                maxStack = new ArrayDeque<>();
            }else if(op[i].equals("push")) {
                stack.push(vals[i][1]);
                if(!maxStack.isEmpty() && maxStack.peek() > vals[i][1]) {
                    maxStack.push(maxStack.peek());
                }else {
                    maxStack.push(vals[i][1]);
                }
            }else if(op[i].equals("pop")) {
                stack.pop();
                maxStack.pop();
            }else if(op[i].equals("top")) {
                ans[i] = stack.peek();
            }else {
                ans[i] = maxStack.peek();
            }
        }
        return ans;
    }
}