程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode 155 Min Stack(最小棧)

LeetCode 155 Min Stack(最小棧)

編輯:C++入門知識

LeetCode 155 Min Stack(最小棧)


翻譯

設計支持push、pop、top和在常量時間內檢索最小元素的棧。

push(x) —— 推送元素X進棧
pop() —— 移除棧頂元素
top() —— 得到棧頂元素
getMin() —— 檢索棧的最小元素

原文

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.

分析

之前寫過兩道題,分別是用Stack來實現Queue的功能以及用Queue來實現Stack的功能,這裡如果也使用兩個Stack的話就非常容易了。

LeetCode 225 Implement Stack using Queues(用隊列來實現棧)(*)

LeetCode 232 Implement Queue using Stacks(用棧來實現隊列)(*)

class MinStack {
public:
    stack allStack;
    stack minSta;

    void push(int x) {
        if (allStack.empty()) {
            allStack.push(x);
            minSta.push(x);
        }
        else {
            allStack.push(x);
            if (x <= minSta.top()) minSta.push(x);
        }
    }

    void pop() {
        if (allStack.top() == minSta.top()) {
            minSta.pop();
        }
        allStack.pop();
    }

    int top() {
        return allStack.top();
    }

    int getMin() {
        return minSta.top();
    }                                  
};

除了上面的stack,我還用vector實現了:

class MinStack {
public:
    vector allVec;
    vector minVec;

    void push(int x) {
        if (allVec.empty()) {       
            allVec.push_back(x);
            minVec.push_back(x);
        }
        else {
            if (x <= minVec[minVec.size() - 1]) {
                minVec.push_back(x);
            }
            allVec.push_back(x);
        }
    }

    void pop() {
        if (allVec[allVec.size() - 1] == minVec[minVec.size() - 1])
            minVec.erase(minVec.end() - 1);
        allVec.erase(allVec.end() - 1);
    }

    int top() {
        return allVec[allVec.size() - 1];
    }

    int getMin() {
        return minVec[minVec.size() - 1];
    }
};

然而用vector效率反而更低了……

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved