Day 13

剑指offer 30.包含min函数的栈

题目描述

思路–辅助栈

解答

class MinStack {
    Stack<Integer> A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >=x)
        B.add(x);
    }
    public void pop() {
        if(A.pop().equals(B.peek()))
        B.pop();
    }
    public int top() {
       return A.peek();
    }
    public int min() {
        return B.peek();
    }
}


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

剑指offer 31.栈的压入、弹出序列

题目描述

思路–辅助栈

模拟过程。遍历pushed数组，将每一个数都入栈到新的stack中，如果当前的数等于poped[i],stack.pop()弹出该数。最后如果stack为空，返回真

解答

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack=new Stack<>();
        int i=0;
        for(int num:pushed){
            stack.push(num);
            while(!stack.isEmpty() && stack.peek().equals(popped[i])){
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}