代码随想录算法训练营第十天 | leetcode:滑动窗口最大值,前 K 个高频元素

Problem: 239. 滑动窗口最大值

需要注意的地方

* !!!以下内容为PHP手册的一些翻译!!!
* 1) pop() & push()继承自SplDoublyLinkedList,可以应用于SplStack以及SplQueue(即“无脸”)。它与堆栈或队列无关;它只是关于删除/添加元素到列表的末尾;
* 2)shift()unshift()相同的情况:它只是将一个元素添加到列表的开头,如果我们在SplStack或SplQueue上使用它并不重要。
*   所以,是的,$q->pop();将从SplQueue $q中删除*last*元素。
* 3) 但是enqueue()dequeue() *是关于* SplQueue的。FIFO原理是由这些方法实现的,这些方法都是为了队列目的而实现的:
*    enqueue()将一个元素添加到队列的末尾
*    dequeue()从队列的开头删除元素
* 4) 如果你想从*queue*中删除*下一行*元素,使用dequeue()*    如果你想从列表中删除最后一个元素(不管它是队列还是堆栈),使用pop()*    如前所述,SplQueue对象上的push()pop()方法的行为更像是堆栈而不是队列。
* 5) 知道enqueue()dequeue()方法分别是push()shift()方法的别名,
*    我们也可以使用SplQueue:: push()SplQueue:: shift()来达到与SplQueue:: enqueue和SplQueue:: dequeue相同的目的。
  1. 简而言之,需要注意的地方是《SplQueue 类》因为继承自SplDoublyLinkedList的原因,继承的一些方法特性更像栈而不是队列,比如:top指向队列队尾,bottom才是指向队头。
  2. 什么是单调队列。队列没有必要维护窗口里的所有元素,只需要维护有可能成为窗口里最大值的元素就可以了,同时保证队列里的元素数值是由大到小的。那么这个维护元素单调递减的队列就叫做单调队列,即单调递减或单调递增的队列。那么这个维护元素单调递减的队列就叫做单调队列

解题方法

需要设计一个单调队列,分别实现pop(),push(),getMax()方法;

  1. 单调队列中push()的逻辑:在入队列的时候,依次与队尾的元素做比较,比要入队列的元素小的则从队尾pop()弹出来。直到找到大于等于自身的元素。然后入队列。也就是一个排序的过程,只不过不需要维护所有元素。
  2. 单调队列中pop()的逻辑:根据窗口的移动,dequeue()弹出队头的元素。
  3. 单调队列中getMax()的逻辑:经过push的筛选,队头的元素已经是最大的元素。所以直接返回队头元素即可。
  4. 以题目示例为例,输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3,动画如下:

复杂度

时间复杂度:

O(n)

空间复杂度:

O(k)

code

 class Solution {

    private $singleQueue;

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer[]
     */
    function maxSlidingWindow($nums, $k) {
        if (count($nums) == 1|| $k == 1) return $nums;

        $this->singleQueue = new SplQueue();
        // 先将前k的元素放进队列
        for ($i = 0; $i < $k; $i++) {
            $this->singlePush($nums[$i]);
        }
        $result = [];
        $result[] = $this->getMax(); // result 记录前k的元素的最大值
        //先将前k个数据push进数组中,后续当$i++ 后移时就可以统一记录最大值
        for ($i = $k; $i < count($nums); $i++) {
            // 滑动窗口移除最前面元素
            $this->singlePop($nums[$i - $k]); 
            // 滑动窗口前加入最后面的元素
            $this->singlePush($nums[$i]); 
            // 记录对应的最大值
            $result[]= $this->getMax(); 
        }
        return $result;
    }
     function singlePop($val){
         //$this->singleQueue继承自SplDoublyLinkedList,所以更像栈,由于栈的头尾与队列头尾相反,所以使用继承方法时,需要注意头尾方向。
         // 滑动窗口移除最前面元素时,需要判断是否等于最大值,如果不等于,那么不用移除,因为在push的时候已经被筛选掉了
         if(!$this->singleQueue->isEmpty() && $this->singleQueue->bottom() == $val){
            $this->singleQueue->dequeue();
         }
     }

     function singlePush($val){
         //判断队列尾部元素是否小于准备入队列元素,是则从尾部弹出,直到大于等于队列尾部元素,然后入队列
         while(!$this->singleQueue->isEmpty() && $this->singleQueue->top() < $val){
             //从队列尾部弹出元素
             $this->singleQueue->pop();
         }
         $this->singleQueue->enqueue($val);
     }

     function getMax(){
         //经过singlePush筛选,队列头部值是最大。
         return $this->singleQueue->bottom();
     }

}

Problem: 347. 前 K 个高频元素

关于php优先级队列《SplPriorityQueue》介绍

!!!以下内容为PHP手册优先级队列《SplPriorityQueue》的一些方法翻译!!!

public const int EXTR_BOTH; //与setExtractFlags搭配提取优先级和值
public const int EXTR_PRIORITY; //与setExtractFlags搭配只提取优先级
public const int EXTR_DATA; //与setExtractFlags搭配只提取值

SplPriorityQueue::compare -比较优先级,以便在筛选时将元素正确地放置在堆中
SplPriorityQueue::count -对队列中的元素数量进行计数
SplPriorityQueue::current -返回迭代器指向的当前节点
SplPriorityQueue::extract -从堆的顶部提取节点并向上筛选
SplPriorityQueue::getExtractFlags—获取提取的标志
SplPriorityQueue::insert—通过筛选将元素插入队列中
SplPriorityQueue:: iscorrupt -告知优先级队列是否处于损坏状态
SplPriorityQueue::isEmpty -检查队列是否为空
SplPriorityQueue::key -返回当前节点索引
SplPriorityQueue::next -移动到下一个节点
SplPriorityQueue::recoverFromCorruption -从损坏状态恢复并允许对队列进行进一步操作
SplPriorityQueue::rewind -将迭代器倒回开始(no-op)
SplPriorityQueue::setExtractFlags—设置提取模式
SplPriorityQueue::top -从队列的顶部查看节点
SplPriorityQueue::valid—检查队列中是否有更多节点

--详细可以转至手册地址:https://www.php.net/manual/zh/class.splpriorityqueue.php
--详细使用例程地址:http://www.noobyard.com/article/p-dvwxrekz-kg.html#google_vignette

需要注意的地方

  1. php中《SplPriorityQueue》默认是使用高优先级优先。根据需要修改优先级。
    class CustomedSplPriorityQueue extends SplPriorityQueue
    {
     public function compare($priority1, $priority2): int
     {
         // return $priority1 - $priority2;//高优先级优先
         return $priority2 - $priority1;//低优先级优先
     }
    }
  2. 根据题目设置提取模式。
    setExtractFlags(EXTR_BOTH);//值和优先级都返回
    setExtractFlags(EXTR_PRIORITY); //只返回优先级
    setExtractFlags(EXTR_DATA); //只返回值

解题方法

  1. 遍历目标数组,把每个元素与出现的次数记录为map数组。key为目标数组的值,val为出现的次数。
  2. 遍历map数组,使用优先级队列,设置低优先级优先(小顶堆),使出现频率高的值沉底。其次维持优先级队列长度为k。当超过长度k时,弹出顶部元素,即出现频率低的元素。直到遍历完成。剩余的k个元素即是出现频率最高的k个元素。
  3. 也可以使用高优先级解题(大顶堆),把所有map数组入队列。最后取顶端的k个元素即可。
    代码随想录算法训练营第十天 | leetcode:滑动窗口最大值,前 K 个高频元素

复杂度

时间复杂度:

O(nlogk)

空间复杂度:

O(n)

小顶堆解法

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer[]
     */
    function topKFrequent($nums, $k) {
        $hashMap = [];
        foreach($nums as $key => $val){
            $hashMap[$val]++;
        }
        $splPriorityQueue = new \CustomedSplPriorityQueue();
        //public const int EXTR_BOTH; 值和优先级都返回
        //public const int EXTR_PRIORITY; 只返回优先级
        //public const int EXTR_DATA; 只返回值
        $splPriorityQueue->setExtractFlags(SplPriorityQueue::EXTR_DATA);
        foreach($hashMap as $key => $val){
            //插入优先级队列
            $splPriorityQueue->insert($key, $val);
            //保持优先级队列为k大小
            if($splPriorityQueue->count() > $k){
                $splPriorityQueue->extract();
            }
        }
        $res = [];
        while(!$splPriorityQueue->isEmpty()){
            $res[] = $splPriorityQueue->extract();
        }
        return $res;
    }
}

class CustomedSplPriorityQueue extends SplPriorityQueue
{
    //SplPriorityQueue默认是高优先级优先,重写为低优先级优先
    //当设置为低优先级优先数据结构为小顶堆,小顶堆的实质是二叉树,小的数在二叉树顶,
    //当优先级队列extract()/pop()元素时,会从堆顶开始弹出,保持堆为k大小,则最后留下的就是最大的k个数
    public function compare($priority1, $priority2): int
    {
        // return $priority1 - $priority2;//高优先级优先
        return $priority2 - $priority1;//低优先级优先
    }
}

大顶堆解法

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer[]
     */
    function topKFrequent($nums, $k) {
        $hashMap = [];
        //构建map数组
        foreach($nums as $key => $val){
            $hashMap[$val]++;
        }
        $splPriorityQueue = new SplPriorityQueue();
        //根据高优先级入队列
        foreach($hashMap as $key=>$val) {
            $splPriorityQueue->insert($key,$val);
        }
        $res = [];
        //取前k个值
        for($i = 0; $i < $k; $i++) {
            $res[] = $splPriorityQueue->extract();
        }
        return $res;
    }
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!