[LeetCode]155. Min Stack

题目描述

思路

两个vector
一个vector存储栈
另一个vector存储到目前为止最小值的下标

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        nums = {};
        mins = {};
        minNum = INT_MAX;
    }

    void push(int x) {
        if (x < minNum) {
            minNum = x;
            mins.push_back(nums.size());
        }
        nums.push_back(x);
    }

    void pop() {
        nums.pop_back();
        if (mins.back() >= nums.size())
            mins.pop_back();
        if (nums.size())
            minNum = nums[mins.back()];
        else
            minNum = INT_MAX;
    }

    int top() {
        return nums.back();
    }

    int getMin() {
        return minNum;
    }
private:
    vector<int> nums;
    vector<int> mins;
    int minNum;
};

int main() {
    MinStack minStack;
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    cout << minStack.getMin() << endl;
    minStack.pop();
    cout << minStack.top() << endl;
    cout << minStack.getMin() << endl;

    system("pause");
    return 0;
}