[slide_window]包含min函数的栈

思路：

一开始只是简单的模拟有min的栈，最直白的就是用一个指针或者变量维持最小值，每次插入删除都更新一次，在调用min的时候就是O(1)，但是这个就是每次都要sort的复杂度（不是find，找不到对比的对象，这里小混），基础的就是这么做了。
看了别人的发现是滑动窗口，只不过活动窗口的时候，当前最值的左区是先失效的，所以每一次的最值都不用考虑左界左的情况只需取代他们，最值右区是候选最值，即使不是当前最值也可能在在他左边的旧最值消失后成为新的最值。这道题是反的，每次top走到一个新值和旧的最值对比，旧最值的左边是有可能成为新最值的（统辖新最值的左边），旧最值的右肯定比旧最值先消失，先消失的一端对于没法更新的值可以直接取代，反正他们会先死，没死的时候旧最值也不会死，所以一定轮不到他们，有更新的则成为新最值。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

//23：00--0：36
class Solution {
public:
    void push(int value) {
        stack.push_back(value);
        heap.push_back(value);
        make_heap(heap.begin(), heap.end(), greater<int>());
    }
    void pop() {
        int m = stack.back();
        stack.pop_back();
        auto it = find(heap.begin(), heap.end(), m);
        heap.erase(it);
        make_heap(heap.begin(), heap.end(), greater<int>());
    }
    int top() {
        return stack.back();
    }
    int min() {
        return heap.front();
    }
private:
    vector<int> stack, heap;
};

class Solution2{
public:
    void push(int value) {
        stack.push_back(value);
        //等于也要入栈，如果等于不保存，待会出的时候等于会被出掉（相当于每个元素的是单独的与minStack一一对应的），则丢失min
        if(minStack.empty() || minStack.back() >= value){
            minStack.push_back(value);
        }
    }
    void pop() {
        //只会是等于的时候要pop 维持的minStack，大于不用更新minStack，不可能小于，不然他就会是minStack的最小元素即等于的情况
        if(stack.back() == minStack.back()){
            minStack.pop_back();
        }
        stack.pop_back();
    }
    int top() {
        return stack.back();
    }
    int min() {
        return minStack.back();
    }
private:
    vector<int> stack, minStack;
};


int main() {
    Solution s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(1);
    cout<<s.top()<<s.min();
    s.pop();
    s.pop();
    cout<<s.top();
    cout<<s.min();


    return 0;
}