【leetcode 简单】第四十八题 最小栈分分快三计划

作者:编程技术

安排叁个支撑 push,pop,top 操作,并能在常数时间内搜寻到微小成分的栈。

思路:

那道题对于栈的操作自己都简单,并不是要用队列或然其他数据结构来效仿叁个栈,直接就允许用栈来做。真正难的在于寻觅最小元素,况且还要再固准时期内。

要在入栈以至出栈的还要不停神草兵简政最小成分,首先栈本身是不帮助的,倘诺用数组之类的来记录,那么每回有新因素进来都急需排个序,特别耗费时间。

于是,这种措施玄妙地在历次入栈、出栈时开展简单的加减操作,达到能够一向得到最小成分的结果。在入栈时,入的不是实际上的因素值,而是与当下记下的最小值的差值,要是新入的更加小,就将其设为最小值,此时就确定保障了任何时候能够获得最小值。出栈时,要改正一点都不大值。获取栈顶成分时,因为栈中记录的而不是原始值,所以要与记录的蝇头值实行操作来还原。

出于标题在submit时会用超过int范围的气数来测量检验,所以只可以用long来操作。

  • push(x) -- Push element x onto stack.
  • pop() -- Removes the element on top of the stack.
  • top() -- Get the top element.
  • getMin() -- Retrieve the minimum element in the stack.
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.data = []
        

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        if len(self.data) == 0:
            return self.data.append((x,x))
        else:
            min_num=self.data[-1][1]
            return  self.data.append((x,x)) if min_num > x else self.data.append((x,min_num))
        
        

    def pop(self):
        """
        :rtype: void
        """
        return self.data.pop()

    def top(self):
        """
        :rtype: int
        """
        return self.data[-1][0]
        

    def getMin(self):
        """
        :rtype: int
        """
        return self.data[-1][1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

大意:

设计三个栈,扶植push、pop、top以至在固按期间内搜索最小成分。

  • push(x) -- 将成分x归入栈中。
  • pop() -- 从栈的下边移除成分。
  • top() -- 获取栈顶成分。
  • getMin() -- 检索栈中的最小成分
    例子:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

 

问题:

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) -- Push element x onto stack.
  • pop() -- Removes the element on top of the stack.
  • top() -- Get the top element.
  • getMin() -- Retrieve the minimum element in the stack.
    Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.

Example:

  • push(x) -- 将成分 x 推入栈中。
  • pop() -- 删除栈顶的要素。
  • top() -- 获取栈顶成分。
  • getMin() -- 检索栈中的最小成分。

引以为戒(Java卡塔尔:

public class MinStack {
    Stack<Long> stack;
    long min;

    /** initialize your data structure here. */
    public MinStack() {
        stack=new Stack<Long>();
    }

    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push(0L);
            min = x;
        } else {
            stack.push(x - min);
            if (x < min) min = x;
        }
    }

    public void pop() {
        if (stack.isEmpty()) return;

        long pop = stack.pop();
        if (pop < 0) min = min - pop;
    }

    public int top() {
        long top = stack.peek();
        if (top < 0) return (int)min;
        else return (int)(min   top);
    }

    public int getMin() {
        return (int)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();
 */

合集:https://github.com/Cloudox/LeetCode-Record


查看作者首页

原因: 
Master stack:  4  1  2  1
Min stack: 4 1 
(如果只插入比栈顶小的元素,那么当弹出1 的时候,min stack的1将被弹出,但是此时的最小值其实还是1,但是min stack就已经丢失了这个最小值)

示例:

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • Master stack: 符合规律记录stack进行push, pop, getMin()等操作后stack的情况
  • 【leetcode 简单】第四十八题 最小栈分分快三计划。Min stack:唯有当stack为空,只怕当前要插入的值 <= min stack.peek()小的时候,才插入值,那样就足以确定保障min stack栈顶的成分恒久皆以最小的。

Note: 为有限支撑min stack栈顶的要素永恒都以最小的, pop操作时务供给拓宽三遍决断,剖断pop的那么些因素是还是不是= = min stack栈顶的元素. 假诺相等,那时亟需同不经常候弹出min stack栈顶的要素。

class MinStack {
    Stack<Integer> mainStack = new Stack<Integer>();
    Stack<Integer> minStack = new Stack<Integer>();

    /** initialize your data structure here. */
    public MinStack() {

    }

    public void push(int x) {
        mainStack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
            System.out.println("push min");
        }
    }

    public void pop() {
        int cur = 0;
        if (!mainStack.isEmpty()) {
            cur = mainStack.pop();
        }

        if (!minStack.isEmpty() && cur == minStack.peek()) {
            minStack.pop();
        } 

    }

    public int top() {
        if (!mainStack.isEmpty()) {
            return mainStack.peek();
        }
        return Integer.MIN_VALUE;
    }

    public int getMin() {
        if (!minStack.isEmpty()) {
            return minStack.peek();
        } 
        return Integer.MIN_VALUE;
    }
}

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

** 思路 **

透过在class中注解2个stack来分别记录master stack和min stack

本文由分分快三计划发布,转载请注明来源

关键词: 分分快三计划 Leetcode LeetCode笔记 Stack