<?php
/**
 * 
 */
class Solution
{
    private $queue;
    function __construct()
    {
        $this->queue = new SplQueue;
    }

    /**
     * 239. 滑动窗口最大值
     * 
     * 给你一个整数数组 nums，有一个大小为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
     * 
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer[]
     */
    function maxSlidingWindow($nums, $k) {
        $res = [];
        $queue = new MyMonotonicQueue;
        // 前k个元素入列 
        for ($i = 0; $i < $k; $i++) { 
            $queue->push($nums[$i]);
        }
        // 记录前k的元素的最大值
        $res[] = $queue->front();
        for ($i = $k; $i < count($nums); $i++) {
            $queue->pop($nums[$i - $k]); // 窗口最左端的元素出列
            $queue->push($nums[$i]);     // 窗口最右端的元素入列
            $res[] = $queue->front();
        }
        return $res;
    }

    /**
     * 347. 前 K 个高频元素
     * 
     * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
     * 输入: nums = [1,1,1,2,2,3], k = 2
     * 输出: [1,2]
     * 
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer[]
     */
    // function topKFrequent($nums, $k) {
    //     $map = [];
    //     for ($i=0; $i < count($nums); $i++) { 
    //         $map[$nums[$i]]++;
    //     }

    //     arsort($map);

    //     $res = [];
    //     foreach ($map as $key => $value) {
    //         if ($k <= 0) {
    //             break;
    //         }

    //         $res[] = $key;
    //         $k--;
    //     }

    //     return $res;
    // }
    function topKFrequent($nums, $k) {
        $map = [];
        for ($i = 0; $i < count($nums); $i++) {
            $map[$nums[$i]]++;
        }

        $heap = new MyMinHeap; // 最小堆
        foreach ($map as $key => $value) {
            $heap->insert($key, $value);
            if ($heap->count() > $k) {
                $heap->extract();
            }
        }

        $res = [];
        while ($heap->valid()) {
            $res[] = $heap->current();
            $heap->next();
        }

        return $res;
    }
}

/**
 * 最小堆/小顶堆
 */
class MyMinHeap extends SplHeap
{
    // 比较元素，以便在筛选时将它们正确地放在堆中，
    // 如果value1大于value2则为正整数，如果相等则为0，否则为负整数
    function compare($arr1, $arr2) { 
        // return $value2 - $value1;// 低优先级优先弹出
        $value1 = array_values($arr1);
        $value2 = array_values($arr2);
        if ($value2[0] === $value1[0]) return 0;
        return $value2[0] < $value1[0] ? -1 : 1;// 低优先级优先弹出
    } 
}

/**
 * 最小堆/小顶堆
 */
class MyMinHeap1 extends SplHeap
{
    function compare($value1, $value2) { 
        return $value2 - $value1;// 低优先级优先弹出
    } 
}

/**
 * 最大堆/大顶堆
 */
class MyMaxHeap extends SplHeap
{
    // 比较元素，以便在筛选时将它们正确地放在堆中，
    // 如果value1小于value2则为正整数，如果相等则为0，否则为负整数
    function compare($arr1, $arr2) { 
        // return $value1 - $value2;// 高优先级优先弹出
        $value1 = array_values($arr1);
        $value2 = array_values($arr2);
        // if ($value2[0] === $value1[0]) return 0;
        // return $value2[0] > $value1[0] ? -1 : 1;// 高优先级优先弹出
        return $value1[0] - $value2[0];// 高优先级优先弹出
    } 
}

/**
 * 最大堆/大顶堆
 */
class MyMaxHeap1 extends SplHeap
{
    function compare($value1, $value2) { 
        return $value1 - $value2;// 高优先级优先弹出
    } 
}

// 单调递减队列
class MyMonotonicQueue
{
    private $queue;
    function __construct()
    {
        $this->queue = new SplQueue;
    }

    // 进一个新元素如果比入口元素大，要将入口元素弹出，直到新元素比入口元素小
    function push($val) 
    {
        while (!$this->queue->isEmpty() && $val > $this->queue->top()) {
            $this->queue->pop(); // 入口元素弹出
        }
        $this->queue->enqueue($val);
    }

    // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
    function pop($val) 
    {
        if (!$this->queue->isEmpty() && $this->queue->bottom() == $val) {
            $this->queue->dequeue();
        }
    }

    function front() 
    {
        return $this->queue->bottom();
    }
}

function que2Arr($queue) {
    $arr = [];
    $queue->rewind();
    while ($queue->valid()) {
        $arr[] = $queue->current();
        $queue->next();
    }

    return $arr;
}

class MyQueue {

    /**
     * 232. 用栈实现队列
     * 
     * 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
     * 
     * 说明：
     *      请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
     *      你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
     * 
     * 进阶：
     *      你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
     * 
     */

    private $stackIn = [];
    private $stackOut = [];

    function __construct() {

    }

    /**
     * 将元素 x 推到队列的末尾
     * 
     * @param Integer $x
     * @return NULL
     */
    function push($x) {
        array_push($this->stackIn, $x);
    }

    /**
     * 从队列的开头移除并返回元素
     * 
     * @return Integer
     */
    function pop() {
        $count = count($this->stackOut);
        // 输出栈有值直接返回
        if ($count) {
            return array_pop($this->stackOut);
        }
        // 输出栈无值，从输入栈pop出一个然后push到输出栈
        while (count($this->stackIn)) {
            array_push($this->stackOut, array_pop($this->stackIn));
        }
        return array_pop($this->stackOut);
    }

    /**
     * 返回队列开头的元素
     * 
     * @return Integer
     */
    function peek() {
        $x = $this->pop();
        array_push($this->stackOut, $x);
        return $x;
    }

    /**
     * 如果队列为空，返回 true ；否则，返回 false
     * 
     * @return Boolean
     */
    function empty() {
        return !count($this->stackIn) && !count($this->stackOut);
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * $obj = MyQueue();
 * $obj->push($x);
 * $ret_2 = $obj->pop();
 * $ret_3 = $obj->peek();
 * $ret_4 = $obj->empty();
 */
// $queue = new MyQueue();
// $queue.push(1);
// $queue.push(2);
// $queue.pop(); 注意此时的输出栈的操作
// $queue.push(3);
// $queue.push(4);
// $queue.pop();
// $queue.pop();注意此时的输出栈的操作
// $queue.pop();
// $queue.empty();

echo "<pre>";

$solu = new Solution();

// 优先级队列
$priorityQueue = new SplPriorityQueue;
// $priorityQueue->insert('A', 1);
// $priorityQueue->insert('B', 13);
// $priorityQueue->insert('C', 6);
// $priorityQueue->insert('D', 16);
// $priorityQueue->insert('F', 26);
// $priorityQueue->insert('E', 22);
// $priorityQueue->insert('G', 8);
// $priorityQueue->insert('A', 1);
// $priorityQueue->insert('B', 13);
// $priorityQueue->insert('C', 6);
// $priorityQueue->insert('D', 16);
// $priorityQueue->insert('F', 26);
// $priorityQueue->insert('E', 22);
// $priorityQueue->insert('G', 8);
// print_r($priorityQueue);
// $priorityQueue->extract();
// print_r($priorityQueue);

// // 最大堆
// $myMaxHeap = new MyMaxHeap();
// $myMaxHeap->insert(['A' => 1]);
// $myMaxHeap->insert(['B' => 13]);
// $myMaxHeap->insert(['C' => 6]);
// $myMaxHeap->insert(['D' => 16]);
// $myMaxHeap->insert(['F' => 26]);
// $myMaxHeap->insert(['E' => 22]);
// $myMaxHeap->insert(['G' => 8]);
// print_r($myMaxHeap);
// $myMaxHeap->extract();
// print_r($myMaxHeap);


// 最大堆
$myMaxHeap = new MyMaxHeap1();
$myMaxHeap->insert(1);
$myMaxHeap->insert(13);
$myMaxHeap->insert(6);
$myMaxHeap->insert(16);
$myMaxHeap->insert(26);
$myMaxHeap->insert(22);
$myMaxHeap->insert(8);

print_r($myMaxHeap);
$myMaxHeap->extract();
print_r($myMaxHeap);


// // 最小堆
// $myMinHeap = new MyMinHeap();
// $myMinHeap->insert(['A' => 1]);
// $myMinHeap->insert(['B' => 13]);
// $myMinHeap->insert(['C' => 6]);
// $myMinHeap->insert(['D' => 16]);
// $myMinHeap->insert(['F' => 26]);
// $myMinHeap->insert(['E' => 22]);
// $myMinHeap->insert(['G' => 8]);
// print_r($myMinHeap);
// $myMinHeap->extract();
// print_r($myMinHeap);
// $myMinHeap->extract();
// print_r($myMinHeap);

// // 最小堆
// $splMinHeap = new SplMinHeap();

// // 最大堆
// $splMaxHeap = new SplMaxHeap();