队列、堆排序（239 滑动窗口最大值）

2024-03-18 11:33:58

1. what is queue

queue（队列）是一种FIFO的线性表

2. STL之deque介绍

deque连续存储结构,即其元素在内存上也是连续的。
我们知道连续内存的容器不能随意扩充,因为很容易会越界。但是deque却可以,它创造了内存连续的假象：
其实deque由一段一段构成 ,它是分段连续,而不是内存连续当走向段的尾端时候自动跳到下一段。

deque除具有vector的所有功能外，还具有高效的首/尾端的插入/删除操作。
缺点：占用内存较多

使用方法：

//默认构造函数 创建一个空的deque
    deque<int> c;

    //拷贝构造
    deque<int> c1(c);

    //赋值拷贝
    deque<int> c2 = c1;

    //指定元素个数创建
    deque<int> c3 (5,6);
    for (auto i : c3) {
        cout<< i << ",";
    }
    cout << "deque(个数, 元素)"<<endl;

    //指定区间创建
    deque<int> c4(c3.begin()+2, c3.begin()+3);
    for (auto i : c4) {
        cout<< i << ",";
    }
    cout << "deque(区间, 区间)"<<endl;

    //指定初始化列表创建
    deque<int> c5({2,3,4,5});
    for (auto i : c5) {
        cout<< i << ",";
    }
    cout << "deque({})"<<endl;

    //指定初始化列表创建
    deque<int> c6 = {2,3,4,5};
    for (auto i : c6) {
        cout<< i << ",";
    }
    cout << "deque = {}" <<endl;

3.Heapsort（堆排序）

3.1 heap 堆

回顾一下堆的概念，堆是一棵顺序存储的近似完全二叉树结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

3.2 heap的性质：

设当前元素在数组中以R[i]表示：

Ri <= R2i+1 且 Ri <= R2i+2
它的左孩子结点是：R[2*i+1];
它的右孩子结点是：R[2*i+2];
它的父结点是：R[(i-1)/2];
3.3 堆排序
由上面的介绍我们可以看出堆的第一个元素要么是最大值（大顶堆），要么是最小值（小顶堆），这样在排序的时候（假设共n个节点），直接将第一个元素和最后一个元素进行交换，然后从第一个元素开始进行向下调整至第n-1个元素。所以，如果需要升序，就建一个大堆，需要降序，就建一个小堆。堆排序的步骤分为三步:
1、建堆（升序建大堆，降序建小堆）；
2、交换数据；
3、向下调整。

4. 239. Sliding Window Maximum（239 滑动窗口最大值问题）

/*
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.
*/
/*
核心思想是：队首始终保存窗口中最大的元素（滑进窗口的那个数要通过与队尾比较找到属于自己的位置,比队尾大要不断弹出队尾把自己插进去，比队尾小则让自己成为队尾），在窗口滑动过程中检查最大值是否还在窗口内，否则就弹出。这样记录下每次滑动时的队首就行了
*/
class Solution 
{
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) 
    {
        //deque q中存储的是num的下标
        deque<int> q;
        vector<int> maxs;
        if(nums.empty()||k<=0) return maxs;

        for(int i=0;i<nums.size();i++)
        {
            //如果队列不为空 且 队尾对应的num小于当前遍历到的值，则弹出当前队尾 ，直到队尾没有小于i所对应的元素，这样就确保了队首对应的元素始终是最大的。
            while(!q.empty()&&nums[q.back()]<=nums[i]) 
                q.pop_back();
            
            //队尾弹入i
            q.push_back(i);
            
            //检测队首所对应的元素是否还在窗口中，不在则弹出
            if(q.front()<=i-k) 
                q.pop_front();
        
            //只有当i>=窗口大小时才能写入窗口的最大值
            if(i>=k-1) 
                maxs.push_back(nums[q.front()]);
        }
        return maxs;
    }
};

参考链接1：STL标准库-容器-deque

参考链接2：排序六堆排序

码农公寓