Min Stack--LeetCode

野性酷女 2022-08-07 12:58 116阅读 0赞

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

*  push(x) -- Push element x onto stack.
 *  pop() -- Removes the element on top of the stack.
 *  top() -- Get the top element.
 *  getMin() -- Retrieve the minimum element in the stack.

思路：使用向量存储元素，使用一个栈记录当前最小元素的索引，没压栈就是向向量存储元素，同时向栈中压入当前最小元素的索引。

#include <iostream>
    #include <stack>
    #include <vector>
    using namespace std;
    
    class Stack
    {
          public:
                 Stack()
                 {
                        }
                 ~Stack()
                 {
                         }
                 int getMin()
                 {
                     int index = minIndex.top();
                     return vec[index];
                 }
                 void push(int x)
                 {
                      int index = minIndex.top();
                      vec.push_back(x);
                      if(vec[index] <= x)
                        minIndex.push(index);
                      else
                        minIndex.push(vec.size()-1);
                      }
                 void pop()
                 {
                      vec.pop_back();
                      minIndex.pop();
                      }
                 int top()
                 {
                     return vec.back();
                     }
          private:
                  vector<int> vec;
                  stack<int> minIndex;
    }; 
    
    int main()
    {
        Stack st;
        return 0;
        }