/ 使用一个对象模拟 map 记录左右括号的对应关系
const leftToRight = {
  "(": ")",
  "{": "}",
  "[": "]"
};

// 用数组列出所有左侧括号
const left = ["(", "{", "["]

/**
 * @param {string} s
 * @return {boolean}
 */

function isValid(str) {
  // 先判断是否为空字符串
  if(!str) {
    return true;
  }

  // 初始化 stack 数组
  let stack = [];

  const len = str.length;

  // 遍历字符串
  for(let i=0; i<len; i++) {
    // 读取当前索引字符串所对应的字符
    let ch = str[i];
    // 判读是否为左括号，如果是就 push 相应的右括号到栈中
    if(left.includes(ch)) {
      stack.push(leftToRight[ch])
    } else {
      // 如果遍历字符为右括号，就和当前 pop 出的栈顶部元素作对比（如果栈还存在元素时）
      if(!stack.length || stack.pop() !== ch) {
        return false
      }
    }
  }
  // 遍历字符串后，栈刚好也清空，表示括号完全匹配，返回 true
  return !stack.length;
}

/**
 * @param {number[]} T
 * @return {number[]}
 */

function dailyTemp(arr) {
  const len = arr.length;
  // 初始化递减栈
  let stack = [];
  // 初始化结果数组，长度与输入数组 arr 相同，初始占位值为 0
  let result = (new Array(len)).fill(0);
  // 遍历数组
  for(let i=0; i<len; i++) {
    // 当栈不为空，且当前遍历的元素的值「打破」元素值递减的规定
    // 并将栈顶部元素（是 arr 中元素的索引）出栈，并（索引）差值记录在结果数组中
    while(stack.length && arr[i]>arr[stack[stack.length-1]]) {
      let top = stack.pop();
      let distance = i - top;
      result[top] = distance;
    }
    // 将当前的元素的索引入栈，等待与其后元素作对比
    // 注意栈里存的不是温度值，而是索引值
    stack.push(i)
  }
  // 返回结果数组
  return result;
}

function MinStack() {
  this.stack = [];
  // 辅助的递减栈
  this.stack2 = [];
}

/**
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function (x) {
  this.stack.push(x);
  // 若入栈的值笔递减栈顶部的值（最小值），则推入辅助栈
  if (this.stack2.length === 0 || this.stack2[this.stack2.length - 1] >= x) {
    this.stack2.push(x);
  }
}

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
  // 若 stack 出栈的值与辅助栈 stack2 顶部的元素相同（最小值），则同时将辅助栈顶部值出栈
  // 保证辅助栈顶部的值是栈 stack 最小值
  if (this.stack.pop() === this.stack2[this.stack2.length - 1]) {
    this.stack2.pop()
  }
}

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
  return this.stack[this.stack.length-1]
}

/**
 * return {number}
 */
MinStack.prototype.getMin = function () {
  // 辅助栈 stack2 顶部元素就是原始栈 stack 的最小值
  return this.stack2[this.stack2.length - 1]
}

function MyQueue() {
  // 初始化两个栈
  this.stack1 = [];
  this.stack2 = [];
}

/**
 * Push element to stack1, back of queue
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function (x) {
  this.stack1.push(x)
}

/**
 * Remove the element from in front of queue and return the element
 * @return {number}
 */
MyQueue.prototype.pop = function () {
  // 如果 stack2 为空，将 stack1 所有元素转移到 stack2，元素逆序后再从 stack2 出栈
  if (this.stack2.length === 0) {
    // 当 stack1 不为空时，转移全部元素
    while (this.stack1.length !== 0) {
      this.stack2.push(this.stack1.pop());
    }
  }
  // 出栈在 stack2 中完成
  return this.stack2.pop();
}

/**
 * Get the front element
 * @return {number}
 * 这个方法和 pop 唯一的区别就是没有将定位到的值出栈
 */
MyQueue.prototype.peek = function () {
  if (this.stack2.length === 0) {
    // 当 stack1 不为空时，转移全部元素
    while (this.stack1.length !== 0) {
      this.stack2.push(this.stack1.pop());
    }
  }
  // 返回 stack2 中栈顶元素
  return this.stack2[this.stack2.length - 1];
}

/**
 * Return whether the queue is empty
 * @return {boolean}
 */
MyQueue.prototype.empty = function () {
  // 若 stack1 和 stack2 均为空，那么队列空
  return !this.stack2.length && !this.stack2.length;
}

let queue = [1,2,3,4] // 定义一个双端队列
queue.push(1) // 双端队列尾部入队
queue.pop() // 双端队列尾部出队
queue.shift() // 双端队列头部出队
queue.unshift(1) // 双端队列头部入队

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */

function maxSlideWindow(nums, k) {
  const len = nums.length;
  // 初始化结果数组
  let res = [];
  // 初始化双端队列
  let deque = [];
  // 遍历数组 nums
  for (let i = 0; i < len; i++) {
    // 判断当前元素与双端队列的队尾元素大小关系
    // 队尾元素不断 pop 出队，直至队尾元素大于或等于当前元素
    while (deque.length && nums[i] > nums[deque[deque.length - 1]]) {
      deque.pop()
    }
    // 将当前元素的索引 push 到「重整」好的双端队列中
    deque.push(i);
    // 检查队列的队头元素是否已被排除到窗口之外
    // 通过索引来比较
    while (deque.length && deque[0] <= i - k) {
      // 将队头元素（数组 nums 的索引）出队
      deque.shift();
    }
    // 判断滑动窗口的状态，是否完成第一个窗口的元素遍历
    // 只有被遍历的元素大于 k 时，才在每一次遍历中将双端队列的队首元素 push 到结果数组中
    if (i >= k - 1) {
      res.push(nums[deque[0]]);
    }
  }
  // 返回结果数组
  return res;
}