差值存储 (val - min_value)方法-最小栈题目

方法一：通例方法 除了存储N个元素外还要存储minValue

1. #include <iostream>
2. #include <climits>  // 包含 INT_MAX
3. class Node{
4. public:
5.     Node *next;
6.     int min,val;
7.     Node(){
8.         this->min=INT_MAX;
9.     }
10.     Node(int val){
11.         this->val=val;
12.     }
13.     Node(int val,Node *next){
14.         this->val=val;
15.         this->next=next;
16.     }
17. };
18. class MinStack {
19. public:
20.     Node *root;
21.     MinStack() {
22.         this->root=new Node();
23.     }
24.    
25.     void push(int val) {
26.         Node *node=new Node(val,root->next);
27.         node->min = root->min;
28.         root->next=node;
29.         root->min=min(root->min,val);
30.     }
31.    
32.     void pop() {
33.         Node *cur = root->next;
34.         if(cur->val==root->min){
35.             root->min=cur->min;
36.         }
37.         root->next=cur->next;
38.         delete cur;
39.     }
41.    
42.     int top() {
43.         return root->next->val;
44.     }
45.    
46.     int getMin() {
47.         return root->min;
48.     }
49. };

复制代码

方法二 差值存储

   只用一个栈 stack 存储每个元素相对于 min_value 的差值，通过判定 差值是否小于 0 来确定当前最小值是否被更换，在 pop() 利用时，如果弹出的差值 diff < 0，阐明 min_value 之前被更新，必要规复前一个最小值

1. class MinStack {
2. private:
3.     vector<long long> stack;  // 存储与最小值的差值
4.     long long min_value;      // 当前最小值
5. public:
6.     MinStack() {
7.         min_value=-1;
8.     }
9.    
10.     void push(int val) {
11.        if(stack.empty()){
12.             stack.push_back(0);
13.             min_value=val;
14.        }else{
15.             long long diff=val-min_value;
16.             stack.push_back(diff);
17.             if(diff<0){
18.                 min_value=val;
19.             }
20.        }
21.     }
22.     void pop() {
23.         if(!stack.empty()){
24.            long long diff = stack.back();
25.             stack.pop_back();
26.             if(diff<0){
27.                 min_value=min_value-diff;
28.             }
29.        }
30.     }
32. 在 top() 方法中，我们的栈存储的是与 min_value 的差值，所以 stack.back() 可能是：
33. -大于等于 0：表示该元素比 min_value 大，存的是 diff = val - min_value
34. -小于 0：表示该元素是 min_value 本身，它曾经导致 min_value 变化（说明 val 变成新的最小值）
35.     int top() {
36.         return stack.back()<0?min_value:min_value+stack.back();
37.     }
38.    
39.     int getMin() {
40.         return min_value;
41.     }
42. };

复制代码