淘先锋技术网

首页 1 2 3 4 5 6 7

【LeetCode & 剑指offer刷题】栈与队列题3:30 包含min函数的栈(155. Min Stack)

【LeetCode & 剑指offer 刷题笔记】目录(持续更新中...)

155. Min Stack

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.

 
//实现一个最小栈(要求获取最小值用常数时间)
//方法一:用两个栈,一个栈存数据,一个栈存各阶段最小数
class MinStack
{
private :
    stack < int > s1 ; //存数据
    stack < int > s2 ; //存各阶段最小数
public :
   
    MinStack ()
    {
       
    }
   
    void push ( int x )
    {
        s1 . push ( x );
        if ( s2 . empty () || x <= s2.top ()) s2 . push ( x ); //如果s2为空,或者存入数小于等于之前最小数,则传入s2
    }
   
    void pop ()
    {
        if ( s1 . top () == s2 . top ()) s2 . pop (); //如果pop的是当前极小值,则s2也跟着pop
        s1 . pop ();
    }
   
    int top ()
    {
        return s1 . top ();
    }
   
    int getMin ()
    {
        return s2 . top (); //栈顶元素为当前最小数
    }
};
 
 
比较min栈与max队列
(1)         if ( s2 . empty () || x <= s2 . top () ) s2 . push ( x ); //如果s2为空,或者存入数小于等于之前最小数,则传入s2
(2)
            while (! index . empty () && num [ i ] >= num [ index . back () ] )
                index . pop_back () ; //从队尾依次弹出队列中比当前num值小的元素,同时也能保证队列首元素为当前窗口最大值下标
            index . push_back ( i ); //插入当前索引值,因为可能为其他窗口下的最大值
 
 
 

 

posted @ 2019-01-05 16:41 wikiwen 阅读( ...) 评论( ...) 编辑 收藏