[LintCode/LeetCode] Min Stack/Max Stack

GHOST_349178 發布于2019-08-14 15:14 / 2478人閱讀

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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