算法學習 - 最小棧的實現O(1)時間
來源：程序員人生 發布時間：2014-12-17 08:41:24 閱讀次數：2697次
最小棧
最小棧其實和棧沒有甚么區分的，唯1的區分在于最小棧是可以在O(1)時間內得到當前的棧空間里，最小的值是多少。
最小棧的操作
最小棧的操作和普通棧的操作沒有太大區分，唯1多了1個方法就是getMin()方法，這個方法是用來獲得當前棧內的最小值。其他方法就是Push(), Pop(), Top()...等
在O(n)時間內找到新的最小值
這里就利害了，先說普通的O(n)的方法~得到棧內最小值。是否是只要保護1個Min的變量就能夠呢？不單單是！下面舉例說明。
我們發現Min值是在第1次插入1的時候為1，第4次插入⑴的時候變成⑴，這個時候我們是否是覺得很簡單，只用保護1個Min就能夠了？不是的！假定我們進行操作：Pop(),Pop()操作。我們來看看堆棧里剩下了甚么。
stack 1 2 3
那末Min呢？還是⑴，但其實⑴已被Pop()掉了。假設我們發現最小值被Pop()以后，我們如何更新Min呢？只能從頭遍歷，那末就需要O(n)的時間。
O(1)的辦法
這里說下如何O(1)時間內就找到，保護的變量沒有變化，但是我們在堆棧內寄存的元素需要與Min值產生關聯。
例子：
我們進行一樣的5次Push操作，壓棧順序為1 2 3 ⑴ 4。
- 第1次棧寄存0, Min為1.
- 第2次棧寄存2-Min=1, Min<2 所以繼續為1.
- 第3次棧寄存3-Min=2, Min<3 所以繼續為1.
- 第4次棧寄存⑴-Min=⑵, Min>⑴ 所以Min = ⑴.
- 第5次棧寄存4-Min=5, Min<5 所以繼續為⑴.
大家看明白沒？我們寄存的數為x-Min.
這是Push的操作，當我們進行Pop()的時候怎樣做呢,進行兩次Pop()？
第1次棧頂元素5， 5>0, 彈出，返回 5+Min=4.
第2次棧頂元素⑵, ⑵<0,彈出，返回Min. 并更新Min=Min-(⑵).
那Top呢？
假設棧頂元素為5, 5>0 返回5+Min.
假設棧頂元素為⑵, ⑵<0 返回Min.
大家發現沒？實際上我們壓棧的時候，壓入的元素就是X-Min，那末只要壓入的元素大于Min，那末寄存的都是正數，而當X小于Min的時候，壓入的元素(X-Min)就是負數。
所以彈棧的時候：
遇到正數，直接彈出棧頂元素(X-Min)和Min的和(X-Min+Min)就能夠了。
遇到負數，說明在壓入這個元素的時候Min值有更新，那個時候的Min值被更新為新插入的X. 例如Min=1,插入⑴的時候，棧寄存⑴-Min=⑵,而Min更新為新的X值(⑴).則彈的時候就直接彈出Min就能夠了。那末我們同時也把最小值彈出了，要更新Min,更新為當前Min-(X-下1個Min)此處比較繞，多用例子理解。
代碼實現
我實現了4個版本，其中前兩個版本是O(1)級別的，后兩個是O(n)級別的。第2個版本可能有些瑕疵，假設你們看到代碼哪里毛病請評論，多謝。
1號容器實現
自己寫的結構體。
//
// main.cpp
// MinStack2
//
// Created by Alps on 14/12/3.
// Copyright (c) 2014年 chen. All rights reserved.
//
#include <iostream>
#include <vector>
using namespace std;
class MinStack {
public:
vector<int> stack;
int min;
void push(int x) {
if (stack.empty()) {
stack.push_back(0);
min = x;
}else{
stack.push_back(x-min);
if (x < min) {
min = x;
}
}
}
void pop() {
if (stack.empty()) {
return;
}else{
if (stack.back() < 0) {
min = min - stack.back();
}
stack.pop_back();
}
}
int top() {
if (stack.empty()) {
return NULL;
}
if (stack.back() > 0) {
return stack.back()+min;
}else{
return min;
}
}
int getMin() {
if (stack.empty()) {
return NULL;
}
return min;
}
};
int main(int argc, const char * argv[]) {
// insert code here...
std::cout << "Hello, World!
";
return 0;
}
2號STL的stack實現
在邊沿測試的時候，我的編譯器沒出錯，但是OJ上報WA了。
//
// main.cpp
// MinStack4_leetcode
//
// Created by Alps on 14/12/3.
// Copyright (c) 2014年 chen. All rights reserved.
//
#include <iostream>
#include <stack>
using namespace std;
class MinStack{
public:
stack<long> s;
long min;
void push(int x){
if (s.empty()) {
s.push(0);
min = x;
}else{
s.push(x-min);
if (x < min) {
min = x;
}
}
}
void pop(){
if (s.empty()) {
return;
}else{
if (s.top() < 0) {
min = min - s.top();
}
s.pop();
}
}
int top(){
if (s.empty()) {
return NULL;
}else{
if (s.top() > 0) {
return (int)(min+s.top());
}else{
return (int)min;
}
}
}
int getMin(){
if (s.empty()) {
return NULL;
}else{
return (int)min;
}
}
};
int main(int argc, const char * argv[]) {
int a = ⑵147483648;
MinStack M;
M.push(2147483646);
M.push(2147483646);
M.push(2147483647);
printf("%d
",M.top());
M.pop();
printf("%d
",M.getMin());
M.pop();
printf("%d
",M.getMin());
M.pop();
M.push(2147483647);
printf("%d
",M.top());
printf("%d
",M.getMin());
M.push(a);
printf("%d
",M.top());
printf("%d
",M.getMin());
M.pop();
printf("%d
",M.getMin());
return 0;
}
3號鏈表實現
自己寫的鏈表結構體。
//
// main.cpp
// MinStack3_leetcode
//
// Created by Alps on 14/12/3.
// Copyright (c) 2014年 chen. All rights reserved.
//
#include <iostream>
using namespace std;
class MinStack {
public:
struct StackNode{
int num;
StackNode *next;
};
typedef StackNode* stack;
stack s;
MinStack(){
s = (stack)malloc(sizeof(struct StackNode));
s->next = NULL;
}
int min;
void push(int x) {
if (s->next == NULL) {
stack node = (stack)malloc(sizeof(struct StackNode));
node->num = x;
node->next = s->next;
s->next = node;
min = x;
}else{
stack node = (stack)malloc(sizeof(struct StackNode));
node->num = x;
node->next = s->next;
s->next = node;
if (x < min) {
min = x;
}
}
}
void pop() {
if (s->next == NULL) {
return;
}else{
stack temp = s->next;
if (min == s->next->num && s->next->next != NULL) {
s->next = s->next->next;
free(temp);
min = s->next->num;
for (stack loop = s->next; loop != NULL; loop = loop->next) {
if (min > loop->num) {
min = loop->num;
}
}
}else{
s->next = s->next->next;
free(temp);
}
}
}
int top() {
if (s->next == NULL) {
return NULL;
}
return s->next->num;
}
int getMin() {
if (s->next == NULL) {
return NULL;
}
return min;
}
};
int main(int argc, const char * argv[]) {
MinStack MinS;
MinS.push(⑴);
MinS.push(0);
MinS.push(2);
MinS.push(⑵);
printf("%d
",MinS.top());
MinS.pop();
MinS.pop();
MinS.pop();
printf("%d
",MinS.getMin());
return 0;
}
4號容器實現
最古老的版本。
//
// main.cpp
// MinStack_leetcode
//
// Created by Alps on 14/12/2.
// Copyright (c) 2014年 chen. All rights reserved.
//
#include <iostream>
#include "vector"
using namespace std;
class MinStack {
public:
struct StackNode{
int num;
int min;
};
vector<StackNode> stack;
void push(int x) {
if (stack.empty()) {
StackNode S = {x,x};
stack.push_back(S);
}else{
if (x < stack.back().min) {
StackNode S = {x,x};
stack.push_back(S);
}else{
StackNode S = {x,stack.back().min};
stack.push_back(S);
}
}
}
void pop() {
if (stack.empty()) {
}else{
stack.pop_back();
}
}
int top() {
if (stack.empty()) {
return NULL;
}
return stack.back().num;
}
int getMin() {
if (stack.empty()) {
return NULL;
}
return stack.back().min;
}
};
int main(int argc, const char * argv[]) {
MinStack minstack;
minstack.push(⑴);
minstack.push(1);
printf("%d %d
",minstack.top(), minstack.getMin());
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
