[LintCode/LeetCode] Min Stack/Max Stack

GHOST_349178 发布于2019-08-14 15:14 / 2458人阅读

Problem

Implement a stack with min() function, which will return the smallest number in the stack.

It should support push, pop and min operation all in O(1) cost.

Example

push(1)
pop() // return 1
push(2)
push(3)
min() // return 2
push(1)
min() // return 1

Note

min operation will never be called if there is no number in the stack.
注意在push()里的条件，minstack.peek() >= number，保证最小值在minstack中。

valueOf(String) returns a new java.lang.Integer, which is the object representative of the integer,
whereas parseInt(String) returns a primitive integer type int.
intValue is an instance method whereby parseInt is a static method.
Moreover, Integer.parseInt(s) can take primitive datatype as well.

Solution

Min Stack

updated 2018-9

class MinStack {

    Stack stack = new Stack<>();
    Stack minstack = new Stack<>();
    /** initialize your data structure here. */
    public MinStack() {
        
    }
    
    public void push(int x) {
        stack.push(x);
        if (minstack.isEmpty() || minstack.peek() >= x) minstack.push(x);
    }
    
    public void pop() {
        if (!stack.isEmpty() && !minstack.isEmpty() && minstack.peek().equals(stack.peek())) minstack.pop();
        stack.pop();
    }
    
    public int top() {
        if (stack.isEmpty()) return 0;
        else return stack.peek();
    }
    
    public int getMin() {
        if (minstack.isEmpty()) return 0;
        else return minstack.peek();
    }
}

Min Stack -- without using Stack class

class MinStack {

    /** initialize your data structure here. */

    private Node head;
    
    private class Node {
        int val;
        int min;
        Node next;
        private Node(int min, int val, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }
    
    public void push(int x) {
        if (head == null) {
            head = new Node(x, x, null);
        } else {
            head = new Node(Math.min(head.min, x), x, head);
        }
    }
    
    public void pop() {
        head = head.next;
        return;
    }
    
    public int top() {
        return head.val;
    }
    
    public int getMin() {
        return head.min;
    }
}

/**
 * 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.getMin();
 */

MAX STACK

public void push(int x) {
    if (maxStack.isEmpty() || maxStack.peek() <= x) maxStack.push(x);
    stack.push(x);
}
public int pop() {
    if (maxStack.peek().equals(stack.peek())) maxStack.pop();
    return stack.pop();
}
public int max() {
    return maxStack.peek();
}

云服务器 GPU云服务器 Stack Error.stack full-stack stack-trace

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65485.html

[LintCode/LeetCode] Trapping Rain Water [栈和双指针]

摘要：一种是利用去找同一层的两个边，不断累加寄存。双指针法的思想先找到左右两边的第一个峰值作为参照位，然后分别向后向前每一步增加该位与参照位在这一位的差值，加入，直到下一个峰值，再更新为新的参照位。 Problem Given n non-negative integers representing an elevation map where the width of each bar i...

bluesky 2019-08-14 15:19 评论0 收藏0
[LintCode/LeetCode] Binary Tree InOrder Traversal

摘要：递归法不说了，栈迭代的函数是利用的原理，从根节点到最底层的左子树，依次入堆栈。然后将出的结点值存入数组，并对出的结点的右子树用函数继续迭代。 Problem Given a binary tree, return the inorder traversal of its nodes values. Example Given binary tree {1,#,2,3}, 1 ...

tomorrowwu 2019-08-14 15:39 评论0 收藏0
[LintCode/LeetCode] Binary Tree Zigzag Level Orde

Problem Given a binary tree, return the zigzag level order traversal of its nodes values. (ie, from left to right, then right to left for the next level and alternate between). Example Given binary tr...

AlphaGooo 2019-08-14 15:40 评论0 收藏0
[LintCode/LeetCode] Binary Tree Preorder Traversal

摘要：当你被的时候，人家问，一定要说，当然可以啦所以，不用，怎么办幸好，这是一道的题目，只要逐层遍历，就可以了。所以，试一试用堆栈的做法吧记得的特点是后入先出哦 Problem Given a binary tree, return the preorder traversal of its nodes values. Example Given: 1 / 2 3 ...

Vixb 2019-08-14 15:39 评论0 收藏0
[LintCode/LeetCode] Flatten Nested List Iterator

摘要：首先，根据迭代器需要不断返回下一个元素，确定用堆栈来做。堆栈初始化数据结构，要先从后向前向堆栈压入中的元素。在调用之前，先要用判断下一个是还是，并进行的操作对要展开并顺序压入对直接返回。 Problem Given a nested list of integers, implement an iterator to flatten it. Each element is either...

spacewander 2019-08-14 15:45 评论0 收藏0