滑动窗口最大值 && 搜索二维矩阵 II

• 滑动窗口最大值 && 搜索二维矩阵 II
  • 滑动窗口最大值
    • 题目详情
    • 解题思路
    • 代码实现
  • 搜索二维矩阵 II
    • 题目详情
    • 解题思路
    • 代码实现

滑动窗口最大值

题目详情

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

解题思路

使用一个单调递减的队列，队列中存储的是元素的索引，队列头部的索引对应的元素是当前窗口中的最大值。具体的解题步骤为：

1. 初始化一个空的单调队列。

2. 遍历数组中的每个元素，对于每个元素的操作为：

   • 如果单调队列不为空，并且当前元素大于队列尾部的元素，那么就不断地从队列尾部移除元素，直到队列为空或者队列尾部的元素大于当前元素。

   • 将当前元素的索引加入到队列尾部。

   • 如果队列头部的索引已经不在滑动窗口内（即，头部索引小于当前元素的索引减去窗口大小加一），那么就从队列头部移除元素。

   • 如果已经遍历了至少 k 个元素，那么就将队列头部的元素加入到结果数组中。

3. 返回结果数组。

代码实现

var maxSlidingWindow = function(nums, k) {
  var pop = function(queue, num) {
    while (queue.length && queue[queue.length - 1] < num) {
      queue.pop()
    }
    queue.push(num)
  }
  const queue = []
  const res = []
  //将前k项元素放入队列
  for (let i = 0; i < k; i++) {
    pop(queue, nums[i])
  }
  for (let i = k; i <= nums.length; i++) {
    res.push(queue[0])
    if (queue[0] === nums[i - k]) {
      queue.shift()
    }
    pop(queue, nums[i])
  }
  return res
};

搜索二维矩阵 II

题目详情

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

解题思路

从矩阵的右上角开始搜索，如果当前元素等于目标值，那么就返回 true；如果当前元素小于目标值，那么就向下移动一行；如果当前元素大于目标值，那么就向左移动一列。重复这个过程，直到找到目标值或者搜索区域为空。

代码实现

function searchMatrix(matrix: number[][], target: number): boolean {
  if (matrix == null || matrix.length == 0) {
    return false;
  }
  let row = 0;
  let col = matrix[0].length - 1;
  while (row < matrix.length && col >= 0) {
    if (matrix[row][col] > target) {
      col--;
    } else if (matrix[row][col] < target) {
      row++;
    } else {
      return true;
    }
  }
  return false;
}