Day11.一刷数据结构算法(C语言版) 239滑动窗口最大值；347前K个高频元素

        今天就两道题，但是有点难，争取理解吧。

---

一.239滑动窗口最大值

        之前讲的都是栈的应用，这次该是队列的应用了。

        本题算比较有难度的，需要自己去构造单调队列，建议先看视频来理解。 

        题目链接/文章讲解/视频讲解：代码随想录

        1.思路分析

        本道题的解题思路推荐观看下方视频，然后再对照具体代码进行学习。思路比较复杂，这里就不写文字说明了，还请认真观看视频，方便读懂之后的代码详解。

        单调窗口最值

 

        2.代码详解

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
    int n = numsSize;
    int queue[n]; //队列
    int front = 0, rear = -1; //队首 队尾
    int left = 0, right = 0; //窗口左下标 窗口右下标
    while (right < n) { //窗口右移至终点
        while (rear >= front && nums[right] > queue[rear]) rear--; //维护队列的单调性（非递增），即保证队首元素就是当前窗口的最大值
        queue[++rear] = nums[right++]; //入队下一个窗口可能的最大值
        if (left + k <= right) { //窗口大小大于k
            if (nums[left] == queue[front]) front++; //如果最大值已经在窗口的左边，则将它永久出队
            else nums[left] = queue[front]; //否则记录最大值进原数组中
            left++; //左框右移
        }
    }
    *returnSize = n - k + 1;
    return nums; //返回原数组
}

         （代码来自leetcode，具体链接：滑动窗口最大值代码来源）

---

 二.347前K个高频元素（先挖个坑）

        大/小顶堆的应用， 在C++中就是优先级队列 

        本题是大数据中取前k值 的经典思路，了解想法之后，不算难。

        题目链接/文章讲解/视频讲解：代码随想录

        1.思路分析

        这道题我第一反应是用哈希表统计元素出现次数，然后我在官网上找到了同样也是用哈希表来实现的题解,具体代码我会在下方分享。

        大概思路:

1. 用哈希表统计每个数对应出现的次数
2. 创建一个二元组，将统计出来的键值对分别加入二元组中
3. 对二元组中的出现次数进行降序排序
4. 取前k个即可

        不过我看大小堆都是用的c++,对于c语言版本的应用，我还没细想，先挖个坑吧。

        2.代码详解

struct HashEntry {
    int key;
    int val;
    UT_hash_handle hh;
};
 
void hashAddItem(struct HashEntry** obj, int key) {
    struct HashEntry* pEntry = NULL;
    HASH_FIND_INT(*obj, &key, pEntry);
    if (pEntry != NULL)
    {
        pEntry->val++;
    }
    else
    {
        pEntry = malloc(sizeof(struct HashEntry));
        pEntry->key = key;
        pEntry->val = 1;
        HASH_ADD_INT(*obj, key, pEntry);
    }
 
}
int temp(const void* a1, const void* b1)
{
	int* a = *(int**)a1;
	int* b = *(int**)b1;
	return  b[1]-a[1];
}
 
int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){
    struct HashEntry* cnt = NULL;
    int* res=malloc(sizeof(int)*k);
    *returnSize=0;
    for(int i=0;i<numsSize;i++)
    {
        hashAddItem(&cnt,nums[i]);
    }
    struct HashEntry* s;
    int count=0;
    for (s = cnt; s != NULL; s = s->hh.next) {
        count++;
    }
    int** que=malloc(sizeof(int*)*count);
    int n=0;
    for (s = cnt; s != NULL; s = s->hh.next) {
        que[n]=malloc(sizeof(int)*2);
        que[n][0]=s->key;
        que[n++][1]=s->val;
    }
    qsort(que, count, sizeof(int*), temp);
    for(int i=0;i<k;i++)
    {
        res[(*returnSize)++]=que[i][0];
    }
    return res;
}

        (代码来自leetcode,具体链接:前K个高频元素代码来源)

---

        今天状态不佳，所以博客写的有点潦草，还请见谅。

        如果你有问题或者有其他想法，欢迎评论区留言，大家可以一起探讨。