算法学习 - 最小栈的实现O(1)时间
最小栈最小栈其实和栈没有甚么区分的，唯1的区分在于最小栈是可以在O(1)时间内得到当前的栈空间里，最小的值是多少。 最小栈的操作最小栈的操作和普通栈的操作没有太大区分，唯1多了1个方法就是getMin()方法，这个方法是用来获得当前栈内的最小值。其他方法就是Push(),Pop(),Top()...等 在O(n)时间内找到新的最小值这里就利害了，先说普通的O(n)的方法~得到栈内最小值。是否是只要保护1个Min的变量就能够呢？不单单是！下面举例说明。
我们发现Min值是在第1次插入 stack 1 2 3
那末 O(1)的办法
这里说下如何O(1)时间内就找到，保护的变量没有变化，但是我们在堆栈内寄存的元素需要与Min值产生关联。
大家看明白没？我们寄存的数为x-Min.
那Top呢？
大家发现没？实际上我们压栈的时候，压入的元素就是X-Min，那末只要压入的元素大于Min，那末寄存的都是正数，而当X小于Min的时候，压入的元素(X-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.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;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |