代码随想录DAY13 || 239.滑动窗口最大值 347. 前K个高频元素

 239.滑动窗口最大值

思路：单调队列；先把前 K 个元素的数组下标入队，如果当前元素大于或等于队尾元素，出队一次；如果小于，该元素入队；第一个窗口处理完以后，队头元素存入结果数组；然后从下标第K个元素开始继续遍历nums，入队与处理第一个窗口一样，只是出队时要注意，每当入队一个元素，应当注意队头元素（就是数组下标）是否小于（当前数组元素下标减去 K +1），小于就将其出队，保持窗口中只有 K 个元素；直到数组遍历结束

注意：

新数组中一共有（numsSize - k + 1）个元素

队列里存放的是数组下标，这让我们很容易地判断什么时候出队

又忘记给 *returnedSize 赋值了！！！

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize){
    int left = 0,right = 0,t = 0;
    int queue[numsSize];
    int *maxnum = malloc(sizeof(int)*(numsSize-k+1));
    for(int i=0; i<k; i++){
        while(left<right && nums[i]>=nums[queue[right-1]])
        {
            right--;
        }
        queue[right++] = i;
    }
    
    maxnum[t++] = nums[queue[left]];
    for(int i=k; i<numsSize; i++){
        while(left<right && nums[i]>=nums[queue[right-1]])
        {
            right--;
        }
        queue[right++] = i;
        if(queue[left] < (i-k+1))
        {
            left++;
        }
       maxnum[t++] = nums[queue[left]];
    }
    *returnSize = t;
    return maxnum;
}

347.  前K个高频元素 

class Solution {
public:
        class cmp
        {
            public:
            bool operator()(const pair<int,int>& lhs, const pair<int ,int>& rhs)
            {
                return lhs.second > rhs.second;
            }
        };
        //小顶堆 
        //通过频率排序
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> min_que;
       
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int ,int>map;
        for(int i=0; i<nums.size(); i++){
            map[nums[i]]++;
        }
        //统计元素出现频率  
        //定义一个小顶堆，大小为k
        for(unordered_map<int,int>::iterator it=map.begin(); it!=map.end(); it++)
        {
            min_que.push(*it);
            if(min_que.size()>k)
            min_que.pop();
        }
        //用固定大小为k的小顶堆全面扫描所有元素的频率
        vector<int> ret(k);
        for( int i=k-1; i>-1; i--)
        {
            ret[i] = min_que.top().first;
            min_que.pop();
        }
        //将前K个高频元素存入数组，由于小顶堆先弹出的是最小的，所   从后往前依次存入
        return ret;
    }
};