2023.9.22/24/25保持顺序删除链表元素，滑动窗口最大值，最小的k个数，第k大，数据流中的中位数

保持顺序删除链表元素

用两个指针，一个指向删完后的元素，一个指向当前遍历到的元素，如果当前遍历到的元素满足条件，就和当前元素交换位置，即当前位置上的元素并不重要

滑动窗口最大值

当窗口长度大于数组长度时，返回空

构造一个队列，用i指针遍历数组每个下标，遍历到时，判断队列中元素和自己的大小关系

去掉比自己先进队列的小于自己的值，因为不小于自己的值，而且还在前面，那么直到它退出队列都不可能为最大值，因为我比它们都大，只要我不出队列，最大值就轮不到它们，而它们又比我先进队列，所以是无用元素，直接出。因为我来了，所以队列中比我小的（比我先入队，但我现在已入队）就再不可能登场，直到出队。

而对于那些比自己大的元素，就不删除，因为有它们顶着，但是它们先入队列，就会比自己先出队列，它们一出，我就有可能是最大值，所以我依然要入队列，而且是在队尾。后面如果有比我大的元素，那我就需要出去，因为此时就算最大的出栈了，我也不可能为最大值

队列记录每个元素的下标，那么队头元素就是当下窗口的最大元素，每次就输出队头即可，i-size+1为固定当前窗口的尾端与长度时所确定的窗口起始位置，那么就要保证队头确实是在窗口中，即front>=i-size+1,一旦小于，那就是窗口不覆盖了，就需要出了

for (int i = size; i < num.size(); i++) {
    res.push_back(num[dp.front()]);
    while (!dq.empty() && dq.front() < (i - size + 1)) {
        dq.pop_front();
    }while (!dq.empty() && num[dq.back()] < num[i]) {
        dq.pop_back();
    }dq.push_back(i);
    res.push_back(num[dq.front()]);
}

最小的k个数（含重复元素）

用优先队列，固定k个数，后面如果比堆顶元素小，就入堆，否则就向后遍历

第K大

停止时，右指针所指元素比基质大，就要把它放到此时左指针上，让后让左指针向后，去找比基值小的，找到之后就让右指针的值为找到的左指针所值元素，一直到左右指针重合，此时就是基值该在的位置，并返回

在主方法中，如果最后返回的值就是k，那直接返回a[k],

如果比k大，就说明k被囊括在这个区间里，然后以[low,p-1]为区间接着递归找k大的元素

如果比k小，就说明在后面的那个区间里，需要在那个区间里去找，只不过就不是第k大的元素，而是k-(p-low+1)，k是第k个数，p是第p个数，Low~p有p-low+1个数

数据流中中位数

插入排序操作：就是让元素和数组中元素比较，直到遇到一个不小于它的元素，就插在它的前面，每个元素都这样做，就可以得到一个递增排序的数列

表达式求值

栈的特点就在于可以调整顺序，即计算的顺序，如果遇到高优先级的，就可以优先计算而不是后入后出，

可以用isdigit（）判断是否为数字，字符转数字要-’0‘

在国王游戏中，

至少需要保证的一个排序就是爆表音量大的排在前面（不对）

实值：先后移再加元素

虚指：先放元素后移动