首页 > 代码库 > 算法学习 - 最小栈的实现O(1)时间
算法学习 - 最小栈的实现O(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!\n";
- return 0;
- }
在边缘测试的时候,我的编译器没出错,但是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 = -2147483648;
- MinStack M;
- M.push(2147483646);
- M.push(2147483646);
- M.push(2147483647);
- printf("%d\n",M.top());
- M.pop();
- printf("%d\n",M.getMin());
- M.pop();
- printf("%d\n",M.getMin());
- M.pop();
- M.push(2147483647);
- printf("%d\n",M.top());
- printf("%d\n",M.getMin());
- M.push(a);
- printf("%d\n",M.top());
- printf("%d\n",M.getMin());
- M.pop();
- printf("%d\n",M.getMin());
- return 0;
- }
自己写的链表结构体。
- //
- // 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(-1);
- MinS.push(0);
- MinS.push(2);
- MinS.push(-2);
- printf("%d\n",MinS.top());
- MinS.pop();
- MinS.pop();
- MinS.pop();
- printf("%d\n",MinS.getMin());
- return 0;
- }
最古老的版本。
- //
- // 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(-1);
- minstack.push(1);
- printf("%d %d\n",minstack.top(), minstack.getMin());
- return 0;
- }
算法学习 - 最小栈的实现O(1)时间
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。