文章

每日LeetCode 179-180

2021.5.24 ・ 共 603 字,您可能需要 2 分钟阅读

Tags: LeetCode

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); –> 返回 -3. minStack.pop(); minStack.top(); –> 返回 0. minStack.min(); –> 返回 -2.

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

class MinStack {
    Stack<Integer> a;
    Stack<Integer> b;
    /** initialize your data structure here. */
    public MinStack() {
        a = new Stack<>();
        b = new Stack<>();
    }
    
    public void push(int x) {
        a.push(x);
        if (b.empty() || b.peek() >= x) {
            b.push(x);
        }
    }
    
    public void pop() {
        if (a.pop().equals(b.peek())) {
            b.pop();
        }
        
    }
    
    public int top() {
        return a.peek();
    }
    
    public int min() {
        return b.peek();
    }
}

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如,序列 {1,2,3,4,5} 是某栈的压栈序列,序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列,但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

示例 1:

输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1] 输出:true 解释:我们可以按以下顺序执行: push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

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() == popped[i]) {
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}