栈与队列相关

[txw2018]

有效括号

题目描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

示例1
输入: "()"
输出: true
示例2
输入: "()[]{}"
输出: true
示例3
输入: "([)]"
输出: false

const isValid = function (s) {
  const map = {
    "(": ")",
    "{": "}",
    "[": "]",
  };
  if (!s) return true;
  const stack = [];

  const len = s.length;
  for (let i = 0; i < len; i++) {
    const val = s[i];
    if (["(", "{", "["].indexOf(val) > -1) {
      stack.push(map[val]);
    } else {
      if (!stack.length || stack.pop() !== val) {
        return false;
      }
    }
  }
  return stack.length === 0;
};

每日温度问题

题目描述: 根据每日气温列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

const dailyTemperatures = function (T) {
  const len = T.length;
  const stack = [];
  const res = Array(len).fill(0);
  for (let i = 0; i < len; i++) {
    while (stack.length && T[i] > T[stack[stack.length - 1]]) {
      const top = stack.pop();
      res[top] = i - top;
    }

    stack.push(i);
  }
  return res;
};

滑动窗口问题

题目描述：给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: 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
1 [3 -1 -3] 5 3 6 7
1 3 [-1 -3 5] 3 6 7
1 3 -1 [-3 5 3] 6 7
1 3 -1 -3 [5 3 6] 7
1 3 -1 -3 5 [3 6 7]

const maxSlidingWindow = function (nums, k) {
  const len = nums.length;
  const res = [];
  let left = 0;
  let right = k - 1;
  while (right < len) {
    const max = getMax(nums, left, right);
    res.push(max);
    left++;
    right++;
  }
  return res;
};

function getMax(nums, left, right) {
  if (!nums || !nums.length) {
    return;
  }
  let maxVal = 0;
  for (let i = left; i <= right; i++) {
    if (nums[i] > maxVal) {
      maxVal = nums[i];
    }
  }
  return maxVal;
}
const nums = [1, 3, -1, -3, 5, 3, 6, 7],
  k = 3;
console.log(maxSlidingWindow(nums, k));

用栈实现队列

题目描述：使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。

const MyQueue = function () {
  this.stack1 = [];
  this.stack2 = [];
};
//将一个元素放入队列的尾部。
MyQueue.prototype.push = function (x) {
  this.stack1.push(x);
};
//从队列首部移除元素。
MyQueue.prototype.pop = function (x) {
  if (this.stack2.length === 0) {
    while (this.stack1.length) {
      this.stack2.push(this.stack1.pop());
    }
  }
  return this.stack2.pop();
};
//返回队列首部的元素。
MyQueue.prototype.peek = function () {
  if (this.stack2.length <= 0) {
    while (this.stack1.length != 0) {
      this.stack2.push(this.stack1.pop());
    }
  }
  const stack2Len = this.stack2.length;
  return stack2Len && this.stack2[stack2Len - 1];
};
// 返回队列是否为空。
MyQueue.prototype.empty = function () {
  return !this.stack1.length && !this.stack2.length;
};