题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

【思路1】两个栈Stack和Min，Stack为当前栈中元素，Min为与Stack中元素一一对应的当前栈最小值。

1 class Solution 2 { 3 public: 4     stack
     
       Stack; 5     stack
      
        Min; 6     void push(int value) 7     { 8         Stack.push(value); 9         if(!Min.empty() && Min.top() < value)  10             value = Min.top();11         Min.push(value);12     }    13     void pop()14     {15         Stack.pop();16         Min.pop();17     }    18     int top()19     {20         return Stack.top();21     }    22     int min()23     {24         return Min.top();25     }26 };
      
     

【思路2】使用pair<int,int>从而实现只用一个栈来操作

1 class Solution 2 { 3 public: 4     stack< pair
     
       > Stack; 5     int Min(int a,int b) 6     { 7         return (a < b)?a:b; 8     } 9     void push(int value)10     {11         Stack.push(pair
      
       (value, Stack.empty()?value:Min(value,min())));12     }    13     void pop()14     {15         Stack.pop();16     }    17     int top()18     {19         return Stack.top().first;20     }    21     int min()22     {23         return Stack.top().second;24     }25 };