<?php

class MyStack {

    private $queue;

    /**
     */
    function __construct() {
        $this->queue = new SplQueue;
    }

    /**
     * @param Integer $x
     * @return NULL
     */
    function push($x) {
        $this->queue->enqueue($x);
    }

    /**
     * @return Integer
     */
    function pop() {
        $size = $this->queue->count();
        // 最后一个元素不动
        while (--$size) {
            // var_dump($this->queue->bottom());
            // 拿到队列头部的值，添加到队列的尾部
            $this->queue->enqueue($this->queue->bottom());
            // 队列的头出队列
            $this->queue->dequeue();
        }
        $result = $this->queue->bottom();
        $this->queue->dequeue();

        return $result;
    }

    /**
     * @return Integer
     */
    function top() {
        return $this->queue->top();
    }

    /**
     * @return Boolean
     */
    function empty() {
        return $this->queue->isEmpty();
    }

    function toArray() {
        $arr = [];
        $count = $this->queue->count();
        $this->queue->rewind();
        while ($count--) {
            $arr[] = $this->queue->current();
            echo $this->queue->key() . ' - ' . $this->queue->current() . "<br>";
            $this->queue->next();
        }
        return $arr;
    }
}

/**
 * 
 */
class Solution
{
    /**
     * 20. 有效的括号
     * 
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     * 有效字符串需满足：
     *   1.左括号必须用相同类型的右括号闭合。
     *   2.左括号必须以正确的顺序闭合。
     * 
     * @param String $s
     * @return Boolean
     */
    function isValid($s) {
        $queue = new SplQueue;
        for ($i=0; $i < strlen($s); $i++) { 
            if ($s[$i] == '(') {
                $queue->push(')');
            } elseif($s[$i] == '[') {
                $queue->push(']');
            } elseif($s[$i] == '{') {
                $queue->push('}');
            } elseif ($queue->isEmpty() || $queue->top() != $s[$i]) {
                return false;
            } else {
                $queue->pop();
            }
        }

        return $queue->isEmpty();
    }

    /**
     * 1047. 删除字符串中的所有相邻重复项
     * 
     * 给出由小写字母组成的字符串S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
     * 在 S 上反复执行重复项删除操作，直到无法继续删除。
     * 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
     * 
     * 输入："abbaca"
     * 输出："ca"
     * 
     * @param String $s
     * @return String
     */
    function removeDuplicates($s) {
        $stack = new SplStack;
        for ($i=0; $i < strlen($s); $i++) { 
            // if ($stack->isEmpty() || $stack->top() !== $s[$i]) {
            if ($stack->isEmpty() || $stack->top() !== $s[$i]) {
                $stack->push($s[$i]);
            } else {
                $stack->pop();
            }
        }

        $res = '';
        if (!$stack->isEmpty()) {
            foreach ($stack as $val) {
                $res = $val . $res;
            }
        }

        return $res;
    }

    /**
     * 150. 逆波兰表达式求值
     * 
     * 根据 逆波兰表示法，求表达式的值。
     * 有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
     * 
     * @param String[] $tokens
     * @return Integer
     */
    function evalRPN($tokens) {
        $stack = new SplStack;
        $operators = ['+', '-', '*', '/'];
        foreach ($tokens as $token) {
            if (!in_array($token, $operators)) {
                $stack->push($token);
            } else {
                $token1 = $stack->top();
                $stack->pop();
                $token2 = $stack->top();
                $stack->pop();
                if($token == '+') $stack->push($token2 + $token1);
                if($token == '-') $stack->push($token2 - $token1);
                if($token == '*') $stack->push($token2 * $token1);
                if($token == '/') $stack->push(intval($token2 / $token1));
            }
        }

        return $stack->top();
    }

    /**
     * 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 MyQueue;
        // 前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 SplPriorityQueue
{
    // 比较元素，以便在筛选时将它们正确地放在堆中，
    // 如果value1大于value2则为正整数，如果相等则为0，否则为负整数
    function compare($value1, $value2 ) { 
        // return $value1 - $value2;// 高优先级优先弹出
        return $value2 - $value1;// 低优先级优先弹出
    } 
}

// 单调递减队列
class MyQueue
{
    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;
}

echo "<pre>";

$solution = new Solution;

// $nums = [1,1,1,2,2,3]; $k = 2;
$nums = [4,1,-1,2,-1,2,3]; $k = 2;
var_dump($solution->topKFrequent($nums, $k));exit;

// $stack = new MyStack();
// $stack->push(1);
// $stack->push(2);
// $stack->push(3);
// $stack->pop();
// var_dump($stack->toArray());exit;

// $s = "()";
// $s = "()[]{}";
// $s = "(]";
// $s = "([)]";
// $s = "{[]}";
// $res = $solution->isValid($s);
// var_dump($res);

// $s = "abbaca";
// $s = "azxxzy";
// $s = "aaaaaaaa";
// $res = $solution->removeDuplicates($s);

// $tokens = ["2","1","+","3","*"];
// $tokens = ["4","13","5","/","+"];
// $tokens = ["13","5","/"];
// $tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"];
// $res = $solution->evalRPN($tokens);

// $queue = new SplQueue;

// // 将元素压入队列
// $queue->push(1); // 此时队列中的节点为 1
// $queue->push(2); // 此时队列中的节点为 2 - 1
// $queue->push(3); // 此时队列中的节点为 3 - 2 - 1
// $queue->pop();      // 次数队列中的节点为 2 - 1
// echo json_encode(que2Arr($queue)), "<br>";
// $queue->pop();      // 次数队列中的节点为 1
// echo json_encode(que2Arr($queue)), "<br>";
// $queue->pop();      // 次数队列中的节点为 空

// $queue->enqueue(1); // 此时队列中的节点为 1
// $queue->enqueue(2); // 此时队列中的节点为 2 - 1
// $queue->enqueue(3); // 此时队列中的节点为 3 - 2 - 1
// $queue->dequeue();  // 此时队列中的节点为 3 - 2
// echo json_encode(que2Arr($queue)), "<br>";
// $queue->dequeue();  // 此时队列中的节点为 3
// echo json_encode(que2Arr($queue)), "<br>";
// $queue->dequeue();  // 此时队列中的节点为 空


// $nums = [1,3,-1,-3,5,3,6,7];$k = 3;
// $nums = [4,-2];$k = 2;
$nums = [9,11];$k = 2;
// $nums = [1];$k = 1;
// $nums = [1,-1];$k = 1;
$res = $solution->maxSlidingWindow($nums, $k);
var_dump($res);


// $queue = new SplQueue;

// // 将元素压入队列
// $queue->push(1); // 此时队列中的节点为 1
// $queue->push(2); // 此时队列中的节点为 2 - 1
// $queue->push(3); // 此时队列中的节点为 3 - 2 - 1

// // 队列节点的个数
// $size = $queue->count();
// echo "size = {$size}", "<br>";
// // 注意队列是先进先出(FIFO)，栈是先进后出(FILO)

// // 得到最后入列元素的值
// $top = $queue->top(); // 此时结果为3，队列节点不变
// echo "top = {$top}", "<br>";

// // 得到最先队列元素的值
// $bottom = $queue->bottom(); // 此时结果为1，队列节点不变
// echo "bottom = {$bottom}", "<br>";

// $queue->rewind();
// $current = $queue->current(); // 此时结果为1，队列节点不变
// echo "current = {$current}", "<br>";

// // 得到最先队列元素的值
// $key = $queue->key(); // 此时结果为1，队列节点不变
// echo "key = {$key}", "<br>";

// $current = $queue->current(); // 此时结果为1，队列节点不变
// echo "current = {$current}", "<br>";

// // 得到最先队列元素的值
// $valid = $queue->valid(); // 此时结果为1，队列节点不变
// echo "valid = ".($valid ? 'true' : 'false'), "<br>";

// $queue->next();

// // 得到最先队列元素的值
// $key = $queue->key(); // 此时结果为1，队列节点不变
// echo "key = {$key}", "<br>";

// $current = $queue->current(); // 此时结果为1，队列节点不变
// echo "current = {$current}", "<br>";

// // 得到最先队列元素的值
// $valid = $queue->valid(); // 此时结果为1，队列节点不变
// echo "valid = ".($valid ? 'true' : 'false'), "<br>";

// $queue->next();

// // 得到最先队列元素的值
// $key = $queue->key(); // 此时结果为1，队列节点不变
// echo "key = {$key}", "<br>";

// $current = $queue->current(); // 此时结果为1，队列节点不变
// echo "current = {$current}", "<br>";

// // 得到最先队列元素的值
// $valid = $queue->valid(); // 此时结果为1，队列节点不变
// echo "valid = ".($valid ? 'true' : 'false'), "<br>";

// $queue->next();

// // 得到最先队列元素的值
// $key = $queue->key(); // 此时结果为1，队列节点不变
// echo "key = {$key}", "<br>";

// $current = $queue->current(); // 此时结果为1，队列节点不变
// echo "current = {$current}", "<br>";

// // 得到最先队列元素的值
// $valid = $queue->valid(); // 此时结果为1，队列节点不变
// echo "valid = ".($valid ? 'true' : 'false'), "<br>";

// $queue->next();

// // 得到最先队列元素的值
// $key = $queue->key(); // 此时结果为1，队列节点不变
// echo "key = {$key}", "<br>";

// $current = $queue->current(); // 此时结果为1，队列节点不变
// echo "current = {$current}", "<br>";

// // 得到最先队列元素的值
// $valid = $queue->valid(); // 此时结果为1，队列节点不变
// echo "valid = ".($valid ? 'true' : 'false'), "<br>";

// // 将元素弹出队列
// $queue->pop(); // 此时队列中的节点为 3 - 2
// $queue->pop(); // 此时队列中的节点为 3
// $queue->pop(); // 此时队列中的节点为 空

// // 用isEmpty来判断队列是否为空
// $result = $queue->isEmpty();  // 结果为true
// echo "result = ".($result ? 'true' : 'false'), "<br>";