算法训练day12Leetcode239滑动窗口最大值347前k个高频元素

今日学习文章链接

https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html#%E6%80%9D%E8%B7%AF

239 滑动窗口最大值

题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

 

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
示例 2：

输入：nums = [1], k = 1
输出：[1]
 

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

我的想法

只想到了暴力解法，n*k的复杂度

题目分析

我们需要一个队列，这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。

这个队列应该长这个样子：

class MyQueue {
public:
    void pop(int value) {
    }
    void push(int value) {
    }
    int front() {
        return que.front();
    }
};

每次窗口移动的时候，调用que.pop(滑动窗口中移除元素的数值)，que.push(滑动窗口添加元素的数值)，然后que.front()就返回我们要的最大值。

这么个队列香不香，要是有现成的这种数据结构是不是更香了！

其实在C++中，可以使用 multiset 来模拟这个过程，文末提供这个解法仅针对C++，以下讲解我们还是靠自己来实现这个单调队列。

然后再分析一下，队列里的元素一定是要排序的，而且要最大值放在出队口，要不然怎么知道最大值呢。

但如果把窗口里的元素都放进队列里，窗口移动的时候，队列需要弹出元素。

那么问题来了，已经排序之后的队列 怎么能把窗口要移除的元素（这个元素可不一定是最大值）弹出呢。

其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。C++中没有直接支持单调队列，需要我们自己来实现一个单调队列

不要以为实现的单调队列就是 对窗口里面的数进行排序，如果排序的话，那和优先级队列又有什么区别了呢。

对于窗口里的元素{2, 3, 5, 1 ,4}，单调队列里只维护{5, 4} 就够了，保持单调队列里单调递减，此时队列出口元素就是窗口里最大元素。

此时大家应该怀疑单调队列里维护着{5, 4} 怎么配合窗口进行滑动呢？

设计单调队列的时候，pop，和push操作要保持如下规则：

pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。

我的acm模式代码

#include <vector>
#include <iostream>
#include <deque>



class Solution {
private:
    class MyQueue {
    public:
        std::deque<int> que;
        void pop(int value) {
            if (!que.empty() && value == que.front()) {
                que.pop_front();
            }
        }
        void push(int value) {
            while (!que.empty() && value > que.back()) {
                que.pop_back();
            }
            que.push_back(value);
        }

        int front() {
            return que.front();
        }
    };
public:
    std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
        MyQueue que;
        std::vector<int> result;
        for (int i = 0; i < k; i++) {
            que.push(nums[i]);
        }
        result.push_back(que.front());
        for (int i = k; i < nums.size(); i++) {
            que.pop(nums[i - k]);
            que.push(nums[i]);
            result.push_back(que.front());
        }
        return result;
    }
};

int main() {
    Solution sol;

    // 示例数组和窗口大小
    std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;

    // 调用函数并接收结果
    std::vector<int> result = sol.maxSlidingWindow(nums, k);

    // 打印结果
    std::cout << "最大滑动窗口的元素为: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

347前k个高频元素

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

 

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]
 

提示：

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
 

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

我的想法

创建hash表，每个键对应一个元素，值对应元素出现的次数

题目分析

这道题目主要涉及到如下三块内容：

要统计元素出现频率
对频率排序
找出前K个高频元素
首先统计元素出现的频率，这一类的问题可以使用map来进行统计。

然后是对频率进行排序，这里我们可以使用一种 容器适配器就是优先级队列。

什么是优先级队列呢？

其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？

缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

什么是堆呢？

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

所以大家经常说的大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），如果懒得自己实现的话，就直接用priority_queue（优先级队列）就可以了，底层实现都是一样的，从小到大排就是小顶堆，从大到小排就是大顶堆。

本题我们就要使用优先级队列来对部分频率进行排序。

为什么不用快排呢， 使用快排要将map转换为vector的结构，然后对整个数组进行排序， 而这种场景下，我们其实只需要维护k个有序的序列就可以了，所以使用优先级队列是最优的。

题目要求前 K 个高频元素，那么果断用大顶堆啊。

那么问题来了，定义一个大小为k的大顶堆，在每次移动更新大顶堆的时候，每次弹出都把最大的元素弹出去了，那么怎么保留下来前K个高频元素呢。

而且使用大顶堆就要把所有元素都进行排序，那能不能只排序k个元素呢？

所以我们要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。

大顶堆（也称为最大堆）是一种特殊的完全二叉树。在这种数据结构中，每个父节点的值都大于或等于其子节点的值。这种属性使得大顶堆的根节点总是包含整个堆中的最大值。以下是大顶堆的一些关键特征：

1. 完全二叉树：大顶堆是一种特殊的完全二叉树，这意味着除了最后一层外，每一层都被完全填满，而最后一层的节点尽可能地集中在左侧。

2. 父节点的值大于子节点的值：在大顶堆中，每个节点的值都大于或等于其子节点的值。这适用于每个非叶子节点。

3. 堆顶元素：由于每个父节点的值都大于其子节点，堆的根节点（或称为堆顶）包含了堆中的最大值。

4. 动态结构：尽管大顶堆是有序的，它并不是完全排序的。当添加新元素或移除堆顶元素时，堆会通过一系列的比较和交换操作（称为堆化）来重新调整结构，以维持大顶堆的性质。

5. 应用场景：大顶堆常用于实现优先队列，以及在各种算法中，如堆排序、查找最大元素等。

在C++中，大顶堆可以使用标准库中的 priority_queue 来实现，而无需指定比较函数，因为 priority_queue 默认就是一个大顶堆。例如：

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> maxHeap;

    maxHeap.push(10);
    maxHeap.push(5);
    maxHeap.push(15);

    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }

    return 0;
}

在这段代码中，priority_queue<int> 定义了一个存储整数的大顶堆，堆顶始终是当前堆中的最大值。

acm模式代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
class Solution {
public:
    class mycomparison {
    public:
        bool operator()(const std::pair<int, int>&lhs,const std::pair<int, int>&rhs) {
            return lhs.second > rhs.second;
        }
    };
    std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
        std::unordered_map<int, int> map; //map<nums[i], times>
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }
        //定义一个小顶堆，大小为k
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, mycomparison> pri_que;
        //用固定大小为k的小顶堆，扫描所有频率的数值
        for (std::unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if (pri_que.size() > k) {
                pri_que.pop();
            }
        }
        //找出前k个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
        std::vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};

int main() {
    Solution sol;

    // 测试数据
    std::vector<int> nums = {1, 1, 1, 2, 2, 3,3,3};
    int k = 2;

    // 调用方法
    std::vector<int> topK = sol.topKFrequent(nums, k);

    // 输出结果
    std::cout << "Top " << k << " frequent elements are: ";
    for (int num : topK) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

在你提供的代码片段中，operator() 函数是作为 mycomparison 类的成员定义的。这个操作符重载使得 mycomparison 类成为一个函数对象（也称为仿函数）。这个函数对象被用作 std::priority_queue 的自定义比较器。让我们详细分析这个操作符的功能和作用：

功能分析

bool operator()(const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) {
    return lhs.second > rhs.second;
}

• 参数: operator() 接受两个 std::pair<int, int> 类型的参数，通常表示队列中的元素。在这个场景中，每个 pair 可能代表了一个值及其出现的频率。

• 返回值: 该函数返回一个布尔值，这个布尔值基于两个 pair 对象的 second 元素的比较结果。

• 比较逻辑: lhs.second > rhs.second。这意味着如果 lhs 的 second 值大于 rhs 的 second 值，则返回 true；否则返回 false。

在 std::priority_queue 中的作用

当这个比较器用于 std::priority_queue 时，它决定了队列中元素的顺序。在你的场景中，队列中的元素是 std::pair<int, int> 类型的，通常第一个元素代表实际的值，而第二个元素代表这个值的频率或某种权重。

由于 operator() 是根据 pair 的 second 值来进行比较的，这个优先队列会根据 second 值的大小来组织其元素。由于比较器返回 true 当 lhs.second > rhs.second，这意味着优先队列实际上是一个最小堆——即 second 值较小的元素会被放在队列的更前面。

应用场景

在你的 topKFrequent 方法中，这种比较器适合用于找到频率（second 值）最高的 k 个元素。使用这个比较器，优先队列会保持其大小为 k，并始终弹出具有最小频率的元素。这样，当所有元素都被考虑过后，队列中就剩下了频率最高的 k 个元素。

栈与队列总结

可以出一道面试题：栈里面的元素在内存中是连续分布的么？

这个问题有两个陷阱：

陷阱1：栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中不一定是连续分布的。
陷阱2：缺省情况下，默认底层容器是deque，那么deque在内存中的数据分布是什么样的呢？ 答案是：不连续的，下文也会提到deque。
所以这就是考察候选者基础知识扎不扎实的好问题。

在栈与队列系列中，我们强调栈与队列的基础，也是很多同学容易忽视的点。

使用抽象程度越高的语言，越容易忽视其底层实现，而C++相对来说是比较接近底层的语言。

我们用栈实现队列，用队列实现栈来掌握的栈与队列的基本操作。

接着，通过括号匹配问题、字符串去重问题、逆波兰表达式问题来系统讲解了栈在系统中的应用，以及使用技巧。

通过求滑动窗口最大值，以及前K个高频元素介绍了两种队列：单调队列和优先级队列，这是特殊场景解决问题的利器，是一定要掌握的。