跳到主要内容

栈和队列✅

说一下栈和队列的结构的特点？​

答案

栈的特点：

  1. 栈是一种线性数结构，只能在一端进行插入和删除操作，这一端称为栈顶。
  2. 栈是一种后进先出（LIFO）的数据结构，最后入栈的元素最先出栈。
  3. 栈的操作只能在栈顶进行，插入元素称为入栈，删除元素称为出栈。
  4. 栈的应用场景：函数调用栈、表达式求值、括号匹配等。

队列的特点：

  1. 队列是一种线性数据结构，只能在一端插入元素，在另一端删除元素，分别称为队尾和队头。
  2. 队列是一种先进先出（FIFO）的数据结构，最先入队的元素最先出队。
  3. 队列的操作只能在队头和队尾进行，插入元素称为入队，删除元素称为出队。
  4. 队列的应用场景：任务调度、消息队列、广度优先搜索等。
class Stack {
  constructor () {
    this.stack = []
  }

  push (value) {
    this.stack.push(value)
  }

  pop () {
    return this.stack.pop()
  }

  peek () {
    return this.stack[this.stack.length - 1]
  }

  isEmpty () {
    return this.stack.length === 0
  }
}
exports.default = Stack

Open browser consoleTests

括号匹配​

/**
 * 括号匹配
 * 输入：s = "()[]{}"
 * 输出：true
 * 输入：s = "([)]"
 * 输出：false
 */
function isValid (s) {

}
答案
const brackets = {
  '(': ')',
  '{': '}',
  '[': ']'
}
function isValid (str) {
  const stack = []
  for (let i = 0; i < str.length; i++) {
    const cur = str[i]
    if (cur === '(' || cur === '{' || cur === '[') {
      stack.push(brackets[str[i]])
    } else {
      if (stack.pop() !== cur) {
        return false
      }
    }
  }
  return stack.length === 0
}

module.exports = isValid

Open browser consoleTests

递减栈温度匹配​

/**
 * 给定一个整数数组 T，返回一个新数组，为每个元素 x 找到下一个更大的元素 y，使得 x < y 的最小等待天数。
 * 输入：T [19, 22, 20, 25, 21, 19, 16, 23, 24]
 * 输出：D = [1, 2, 1, 0, 3, 2, 1, 1, 0]
 * 解释初始含义
 * D[0] = 1 因为 19 -> 22 等待 1 天
 * D[1] = 2 因为 22 -> 25 等待 2 天
 * D[2] = 1 因为 20 -> 25 等待 1 天
 * D[3] = 0 因为 25 气温在这之后不会再升高
 * D[4] = 3 因为 21 -> 23 等待 3 天
 * D[5] = 2 因为 19 -> 23 等待 2 天
 * D[6] = 1 因为 16 -> 23 等待 1 天
 * D[7] = 1 因为 23 -> 24 等待 1 天
 * D[8] = 0 因为 24 气温在这之后不会再升高
 */

function dailyTemperatures (T) {

}
答案
/**
 * 1. 初始化一个栈，所有结果赋值为 0
 * 2. 循环温度，取出当前温度
 * 3. 如果栈为空，直接入栈
 * 4. 如果栈不为空，判断当前温度是否大于栈顶温度,如果大于，出栈，计算出栈温度的索引差值，赋值给结果数组,
 * 5. 重复 3，直到栈为空或者当前温度小于等于栈顶温度
 * 6. 如果小于等于，入栈
 * 7. 遍历结束, 直接返回结果
 */
function dailyTemperatures (T) {
  const decreaseStack = []
  // 1. 初始化一个栈，所有结果赋值为 0
  const res = new Array(T.length).fill(0)
  // 2. 循环温度，取出当前温度
  for (let i = 0; i < T.length; i++) {
    const cur = T[i]
    // 3. 如果栈为空，直接入栈
    if (decreaseStack.length === 0) {
      decreaseStack.push(i)
    } else {
      // 4. 如果栈不为空，判断当前温度是否大于栈顶温度,如果大于，出栈，计算出栈温度的索引差值，赋值给结果数组,
      // 5. 重复 3，直到栈为空或者当前温度小于等于栈顶温度
      while (decreaseStack.length > 0 && cur > T[decreaseStack[decreaseStack.length - 1]]) {
        const top = decreaseStack.pop()
        res[top] = i - top
      }
      // 6. 如果小于等于，入栈
      decreaseStack.push(i)
    }
  }
  // 7. 遍历结束, 直接返回结果
  return res
}

module.exports = dailyTemperatures

Open browser consoleTests

最小栈​

/**
 * 设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。
 * push(x) 将元素 x 推入栈中。
 * pop() 删除栈顶的元素。
 * top() 获取栈顶元素。
 * getMin() 检索栈中的最小元素。
 *
 * push(-2)
 * push(0)
 * push(-3)
 * getMin() // 返回 -3
 * pop()
 * top() // 返回 0
 * getMin() // 返回 -2
 *
 */
interface MinStack {
  push (x: number): void
  pop (): void
  top (): number
  getMin (): number
}
答案
/**
 */
class MinStack {
  constructor () {
    this.stack = []
    // 采用递减栈维护最小值
    this.decreaseStack = []
  }

  push (value) {
    this.stack.push(value)
    // 递减栈为空，或者压入值比递减栈栈顶小则推入
    if (this.decreaseStack.length === 0 || value <= this.decreaseStack[this.decreaseStack.length - 1]) {
      this.decreaseStack.push(value)
    }
  }

  pop () {
    const value = this.stack.pop()
    // 如果弹出值等于递减栈栈顶值，则递减栈也弹出
    if (value === this.decreaseStack[this.decreaseStack.length - 1]) {
      this.decreaseStack.pop()
    }
    return value
  }

  top () {
    return this.stack[this.stack.length - 1]
  }

  getMin () {
    return this.decreaseStack[this.decreaseStack.length - 1]
  }
}

exports.default = MinStack

Open browser consoleTests

用栈实现队列​

/**
 * 使用栈实现队列
 * 实现队列的基本操作：enqueue、dequeue、peek、empty
 * enqueue(1)
 * enqueue(2)
 * peek() // 返回 1
 * dequeue() // 返回 1
 * empty() // 返回 false
 * enqueue(3)
 * empty() // 返回 false
 * dequeue() // 返回 2
 * dequeue() // 返回 3
 * empty() // 返回 true
 */
interface StackQueue {
   enqueue(x: number): void;
   dequeue(): number;
   peek(): number;
   empty(): boolean;
}
答案
/**
 * 1. 栈的特点是先进后出，队列的特点是先进先出
 * 2. 用两个栈实现队列，一个栈用来入队，一个栈用来出队
 * 3. 入队时，将元素压入栈 1
 * 4. 出队时，如果栈 2 为空，将栈 1 的元素逐个弹出并压入栈 2，栈 2 出栈
 * 5. 如果栈 2 不为空，直接出栈
 * 6. peek 方法返回栈 2 的栈顶元素
 */
class StackQueue {
  constructor () {
    this.pushStack = []
    this.popStack = []
  }

  enqueue (value) {
    this.pushStack.push(value)
  }

  dequeue () {
    if (this.popStack.length === 0) {
      while (this.pushStack.length > 0) {
        this.popStack.push(this.pushStack.pop())
      }
    }
    return this.popStack.pop()
  }

  peek () {
    if (this.popStack.length === 0) {
      while (this.pushStack.length > 0) {
        this.popStack.push(this.pushStack.pop())
      }
    }
    return this.popStack[this.popStack.length - 1]
  }

  empty () {
    return this.pushStack.length === 0 && this.popStack.length === 0
  }
}

exports.default = StackQueue

Open browser consoleTests

双端队列最近的较大元素​

/**
 * 给定一个数组，返回一个等长的数组，对应索引存放下一个更大元素，如果没有更大的元素则存放 -1。
 * 要求：使用双端队列实现，时间复杂度 O(n)
 *
 * 输入：nums = [2, 1, 2, 4, 3]
 * 输出：[4, 2, 4, -1, -1]
 * 解释：
 * - 2 的下一个更大元素是 4
 * - 1 的下一个更大元素是 2
 * - 2 的下一个更大元素是 4
 * - 4 没有下一个更大元素，返回 -1
 * - 3 没有下一个更大元素，返回 -1
 */
function nextGreaterElement (nums: number[]): number[] {
  // 实现函数
}
答案
/**
 * 查找数组中每个元素的下一个更大元素
 */
function nextGreaterElement (nums) {
  // 1. 初始化结果数组和栈
  const result = new Array(nums.length).fill(-1)
  const stack = []

  // 2. 遍历输入数组中的每个元素
  for (let i = 0; i < nums.length; i++) {
    // 3. 当栈不为空且当前元素大于栈顶索引对应的元素时
    while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
      // 4. 从栈中弹出索引，并用当前元素更新其结果
      const index = stack.pop()
      result[index] = nums[i]
    }
    // 5. 将当前索引压入栈中
    stack.push(i)
  }

  // 6. 返回最终结果数组
  return result
}

module.exports = nextGreaterElement

Open browser consoleTests

滑动窗口​

/**
 * 给定一个整数数组 nums 和一个整数 k，返回数组中每个连续 k 个元素的最大值。
 * 输入：nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
 * 输出：[3, 3, 5, 5, 6, 7]
 */
function maxSlidingWindow (nums: number[], k: number): number[] {
  // finish the function
}
答案
/**
 * 滑动窗口最大值问题解决步骤:
 * 1. 创建双端队列deque存储元素索引，队列中索引对应的元素值保持递减
 * 2. 处理前k个元素:
 *    - 移除队尾小于当前元素的所有索引
 *    - 将当前索引加入队尾
 * 3. 遍历剩余元素(i从k开始):
 *    - 移除队首不在当前窗口范围的索引
 *    - 移除队尾小于当前元素的所有索引
 *    - 将当前索引加入队尾
 *    - 将队首对应的元素(窗口最大值)加入结果数组
 * 4. 返回结果数组
 *
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
function maxSlidingWindow (nums, k) {
  const deque = []
  const result = []

  for (let i = 0; i < nums.length; i++) {
    // 移除队首不在当前窗口范围的索引
    if (deque.length > 0 && deque[0] < i - k + 1) {
      deque.shift()
    }

    // 移除队尾小于当前元素的所有索引
    while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop()
    }

    // 将当前索引加入队尾
    deque.push(i)

    // 将队首对应的元素(窗口最大值)加入结果数组
    if (i >= k - 1) {
      result.push(nums[deque[0]])
    }
  }

  return result
}

module.exports = maxSlidingWindow

Open browser consoleTests

22%