戊辰人博客

青,取之于蓝而青于蓝;冰,水为之而寒于水。

LeetCode编程挑战(No.155 MinStack)

日期:2015年4月6日 作者: 分类:编程 阅读:535

LeetCode 已是一个针对程序员招聘的颇具口碑的准备面试平台。虽然主要针对北美市场,但是内容也能很好的帮助大部分国内的IT面试者。虽然关注好久了,但一直没开始。从今天起正式开始LeeCode编程挑战,计划在今年内完成所有挑战题目。

为了保证题意的准确性,对于官方的题目就不进行翻译了。对于程序员,英文阅读也是编程的基本能力之一。

编程语言:C++

No.155:MinStack

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.

 

我在解题时使用双栈法,即使用一个栈保存栈中数据,一个栈同步保存栈中最小值。

但在提交通过后,官方给出两种思路:

O(n) runtime, O(n) space – Extra stack:

Use an extra stack to keep track of the current minimum value. During the push operation we choose the new element or the current minimum, whichever that is smaller to push onto the min stack.

O(n) runtime, O(n) space – Minor space optimization:

If a new element is larger than the current minimum, we do not need to push it on to the min stack. When we perform the pop operation, check if the popped element is the same as the current minimum. If it is, pop it off the min stack too.

本人使用的是第一种,这种方法占用的内存较多;第二种方法占用内存较少,并未研究成功。我的代码如下:

class MinStack {
    stack<int> s;
    stack<int> sMin;
public:
    void push(int x) {
        s.push(x);
        if(sMin.empty() || x < sMin.top())
            sMin.push(x);
        else
            sMin.push(sMin.top());
    }
    void pop() {
        sMin.pop();
        s.pop();
    }
    int top() {
        return s.top();
    }
    int getMin() {
        return sMin.top();
    }
};

 

标签:,

除非注明,戊辰人博客文章均为原创,转载请以链接形式标明本文地址

本文地址:https://wanglu.info/286.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注