栈/堆/队列刷题(中)

一、滑动窗口的最大值

解法一:双向队列(推荐)

窗口符合先进先出的原则

• 维护一个双向队列，存储数组下标
• 遍历第一个窗口，如果即将进入队列的值大于队列后方的值，依次将较小值拿出来，再加入，保证队列是递增的
• 遍历后续窗口，每次取队头即为最大值，若存在下标越过窗口，将其弹出

class Solution {
    
public:
    vector<int> maxInWindows(const vector<int>& nums, int size) {
    
        vector<int>tmp;
        if(size<=nums.size()&&size!=0)//窗口长度合法进入
        {
    
            deque<int>d;
            for(int i=0;i<size;i++)
            {
    
                while(!d.empty()&&nums[d.back()]<nums[i])//去掉较小值下标
                    d.pop_back();
                d.push_back(i);
            }
            for(int i=size;i<nums.size();i++)
            {
    
                tmp.push_back(nums[d.front()]);
                while(!d.empty()&&d.front()<(i-size+1))//下标要合法
                    d.pop_front();//弹出窗口移走后的值
                while(!d.empty()&&nums[d.back()]<nums[i])
                    d.pop_back();
                d.push_back(i);
            }
            tmp.push_back(nums[d.front()]);
        }
        return tmp;
    }
};

时间复杂度:O(n),数组长度为n，遍历一边数组
空间复杂度:O(m），窗口长度为m

解法二:暴力法

• 第一遍遍历数组每个位置作为窗口起点
• 从每个起点开始遍历窗口长度

class Solution {
    
public:
    vector<int> maxInWindows(const vector<int>& nums, int size) {
    
        vector<int>tmp;
        if(size<=nums.size()&&size!=0)//窗口长要小于数组长，且不为0
        {
    
            for(int i=0;i<=nums.size()-size;i++)//数组后空一个窗口大小，避免越界
            {
    
                int max=INT_MIN;
                for(int j=i;j<i+size;j++)//寻找每个窗口的最大值
                {
    
                    if(nums[j]>max)
                        max=nums[j];
                }
                tmp.push_back(max);
            }
        }
        return tmp;
    }
};

时间复杂度:O(n*m),窗口长度m,数组长度n，双层循环
空间复杂度:O(!),出必要数组存储，未使用额外存储空间

二、最小的K个数

解法一:堆排序(推荐)

用优先队列(大堆)维持K个最小元素

• 利用数组内的K个元素构建一个大小为K的大堆，堆顶为这K个元素的最大值
• 对后续元素，比较与堆顶元素的大小，比堆顶小，将其弹出将较小值入堆，直到数组结束
• 堆顶依次弹出K个数即为结果

class Solution {
    
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
    
        vector<int>tmp;
        if(k==0||input.size()==0||k>input.size())
            return tmp;
        priority_queue<int>q;//优先队列会自动排序
        for(int i=0;i<k;i++)//构建大小为k的堆
            q.push(input[i]);
        for(int i=k;i<input.size();i++)
        {
    
            if(q.top()>input[i])
            {
    
                q.pop();
                q.push(input[i]);                                                                                                                                     
            }
        }
        for(int i=0;i<k;i++)
        {
    
            tmp.push_back(q.top());
            q.pop();
        }
        return tmp;
    }
};

时间复杂度:O(n${\log }_2$k),构建和维护大小为k的堆为${\log }_2$k,还有遍历数组的n
空间复杂度:O(k),堆占用k

解法二:sort排序法

直接将数组升序排序

class Solution {
    
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
    
        vector<int>tmp;
        if(k==0||input.size()==0||k>input.size())
            return tmp;
        sort(input.begin(),input.end());//默认升序排序
        for(int i=0;i<k;i++)
            tmp.push_back(input[i]);
        return tmp;
    }
};

时间复杂度:O(n${\log }_2$n),sort快排时间复杂度
空间复杂度:O(1)

解法三:快排思想

对数组[l, r]一次快排partsort可得到，[l, p), p, [p+1, r)三个区间,[l,p)为小于等于p的值
[p+1,r)为大于等于p的值。
然后再判断p，利用二分法

[l,p), p，也就是p+1个元素（因为下标从0开始），如果p+1 == k, 找到答案
如果p+1 < k, 说明答案在[p+1, r)区间内，
如果p+1 > k , 说明答案在[l, p)内

class Solution {
    
public:
    int partsort(vector<int>&input,int l,int r)
    {
    
        int pivot=input[r-1];//挖坑法，取区间最右值
        int i=l;
        for(int j=l;j<r-1;j++)
        {
    
            if(input[j]<pivot)
                swap(input[i++],input[j]);//将比坑小的值置于数组区间前部
        }
        swap(input[i],input[r-1]);
        return i;
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
    
        vector<int>tmp;
        if(k==0||input.size()==0||k>input.size())
            return tmp;
        int l=0,r=input.size();
        while(l<r)
        {
    
            int p=partsort(input,l,r);
            if(p+1==k)
                return vector<int>({
    input.begin(),input.begin()+k});
            else if(p+1<k)
                l=p+1;
            else
                r=p;
        }
        return tmp;
    }
};

时间复杂度:平均O(n),最坏O(n^2)
空间复杂度:O(1)

三、寻找第k大

解法一:sort

需自定义比较方法，降序排序

class Solution {
    
public:
    static bool cmp(int n1,int n2)
    {
    
        return n1>n2;
    }
    int findKth(vector<int> a, int n, int K) {
    
        // write code here
        sort(a.begin(),a.end(),cmp);
        return a[K-1];
    }
};

时间复杂度:O(n${\log }_2$n),sort快排时间复杂度
空间复杂度:O(1)

解法二:快排+二分法

• 进行一次快排，大的排在左，小的排在右，得到中点p
• 如果p-left+1==k,p即为第k大
• 如果大于k，则第k大在左半段，右区间right缩减为p-1,再次进行该区间的快排
• 如果小于k,则第k大在右半段，左区间left缩减为p+1,且k=k-(p-left+1),排除前面更大的元素

class Solution {
    
public:
    //快速划分，大数在左
    int partsort(vector<int>&a,int left,int right)
    {
    
        int tmp=a[left];
        while(left<right)
        {
    
            while(left<right&&a[right]<=tmp)
                right--;
            if(left==right)
                break;
            else
                a[left]=a[right];
            while(left<right&&a[left]>=tmp)
                left++;
            if(left==right)
                break;
            else
                a[right]=a[left];
        }
        a[left]=tmp;
        return left;
    }
    int quicksort(vector<int>&a,int left,int right,int K)
    {
    
        int p=partsort(a,left,right);//进行一轮划分,p下标左边比它大，右边比它小
        if(K==p-left+1)//若p刚好为第K个点，则找到
            return a[p];
        else if(p-left+1>K)//从头到p超过K个数，目标还在左边
            return quicksort(a,left,p-1,K);//递归左边
        else
            return quicksort(a,p+1,right,K-(p-left+1));
    }
    int findKth(vector<int> a, int n, int K) {
    
        // write code here
        return quicksort(a,0,n-1,K);
    }
};

在牛客网测试中最后一个案例超时
时间复杂度：O(n)，利用二分法缩短了时间——T(N/2)+T(N/4)+T(N/8)+……=T(N)
空间复杂度：O(n)，递归栈最大深度

解法三:快排+二分优化(推荐)

class Solution {
    
public:
    int partition(vector<int>& a, int left, int right, int k){
    
        //随机快排划分
        swap(a[left], a[rand() % (right - left + 1) + left]);
        int tmp = a[left],i = left + 1,j = right;
        while(true){
    
            //小于标杆的在右
            while(j >= left + 1 && a[j] < tmp) 
                j--;
            //大于标杆的在左
            while(i <= right && a[i] > tmp) 
                i++;
            if(i > j) 
                break;
            swap(a[i], a[j]);
            i++;
            j--;
        }
        swap(a[left], a[j]);
        //从0开始，所以为第j+1大
        if(j + 1 == k)
            return a[j];
        //继续划分
        else if(j + 1 < k)
            return partition(a, j + 1, right, k);
        else
            return partition(a, left, j - 1, k);
    }
    int findKth(vector<int> a, int n, int K) {
    
        return partition(a, 0, n - 1, K);
    }
};

每次排序进行一次随机交换，去掉这行代码，最后一个用例就通不过了，估计是没得办法，尝试了一下随机概率，在时间范围内找到了目标数据,解法二加上此句可通过
时间复杂度：O(n)，利用二分法缩短了时间——T(N/2)+T(N/4)+T(N/8)+……=T(N)
空间复杂度：O(n)，递归栈最大深度