【题目】

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

【要求】

1.pop、push、getMin操作的时间复杂度都是O（1）。

2.设计的栈类型可以使用现成的栈结构。

【题解】

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

【要求】

1．pop、push、getMin操作的时间复杂度都是O(1)。

2．设计的栈类型可以使用现成的栈结构。

解题思路：

使用一个辅助栈，里面存的目前栈中的最小值

1 #pragma once 2 #include 
     
       3 #include 
      
        4  5 using namespace std; 6  7 // 8 //实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。 9 //【要求】10 //1．pop、push、getMin操作的时间复杂度都是O(1)。11 //2．设计的栈类型可以使用现成的栈结构。12 //13 //14 //解题思路：15 //    使用一个辅助栈，里面存的目前栈中的最小值16 17 18 class GetMin19 {20 public:21     void PushData(int a)22     {23         Data.push(a);24         if (Min.empty())25             Min.push(a);//当还未存数时，目前栈中的最小值就是第一个数26         else27             Min.push(Min.top() <= a ? Min.top() : a);28         //将新加入的数与栈中的最小值相比，存入新的最小值，以维持Data与Min栈的高度一样29     }30 31     int GetTop()32     {33         if (Data.size())34             return Data.top();35         return -1;36     }37 38     int theMin()39     {40         if (Data.size())41             return Min.top();42         return -1;43     }44 45     void PopData()46     {47         if (Data.size())48         {49             Data.pop();50             Min.pop();51         }52     }53 54 private:55     stack
       
        Data;56     stack
        
         Min;57 };58 59 void main()60 {61     GetMin ss;62     ss.PushData(6);63     cout << ss.theMin() << endl;64     ss.PushData(5);65     cout << ss.theMin() << endl;66     ss.PushData(2);67     cout << ss.theMin() << endl;68     ss.PushData(1);69     cout << ss.theMin() << endl;70     ss.PushData(3);71     cout << ss.theMin() << endl;72     ss.PushData(6);73     cout << ss.theMin() << endl;74 75     ss.PopData();76     cout << ss.theMin() << endl;77     ss.PopData();78     cout << ss.theMin() << endl;79     ss.PopData();80     cout << ss.theMin() << endl;81     ss.PopData();82     cout << ss.theMin() << endl;83 }