498.对角线遍历 | LeetCode 笔记

# 498.对角线遍历

# 题目

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]

链接：https://leetcode-cn.com/problems/diagonal-traverse/ (opens new window)

# 答案

该题目需要总结出：遍历的方向由层数（横纵坐标之和）决定的，偶右上奇左下，这个规律。之后通过遍历总的个数，和控制当前行和列的位置来完成数组的构成。其中需要处理一些临界点，例如向右上方遍历的时候会存在上面和右面两个临界位置。

/**
 * @param {number[][]} mat
 * @return {number[]}
 */
var findDiagonalOrder = function(mat) {
  if (!mat || !mat.length) {
    return [];
  }

  let r = 0;
  let c = 0;
  const rows = mat.length;
  const cols = mat[0].length;
  const res = [];
  
  // 遍历的次数等于总个数
  for (let i = 0; i < rows * cols; i++) {
    res[i] = mat[r][c];
    // 遍历的方向由层数（横纵坐标之和）决定的，偶右上奇左下
    if ((r + c) % 2 === 0) {
      if (c === cols - 1) {
        // 往下移动，准备向左下遍历
        r++;
      } else if (r === 0) {
        // 往右移动，准备向左下遍历
        c++;
      } else {
        // 右上方移动
        c++;
        r--;
      }
    } else {
      if (r === rows - 1) {
        // 向右移动，准备向右上方遍历
        c++;
      } else if (c === 0) {
        // 向下移动，准备向右上方遍历
        r++;
      } else {
        // 左下方移动
        c--;
        r++;
      }
    }
  }

  return res;
};

# 80.删除有序数组中的重复项

# 题目

给你一个有序数组 nums，请你原地删除重复出现的元素，使每个元素最多出现两次，返回删除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5，并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 不需要考虑数组中超出新长度后面的元素。

链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/ (opens new window)

# 答案

题目要求每个元素最多出现两次，那么对于前两个数字我们可以直接保留。现在我们考虑第三个数的情况，由于数组是有序的，如果第三个数和第一个数一样，那么第二个数必定也是一样的，这样就会有三个一样的数字，不符合题意了。所以只要我们保证第一个和第三个数不一样，那么即使第一个数和第二个数一样也是符合题意的。接着我们从第三个数字起遍历，每找到一个与 当前指针前 - 2 位置不同的值就赋值到当前指针位置，并将指针往前移动一位。

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
  let len = 0;
  for (num of nums) {
    if (len < 2 || nums[len - 2] !== num) {
      nums[len++] = num;
    }
  }
  return len;
};

# 502.IPO

# 题目

假设力扣（LeetCode）即将开始 IPO。为了以更高的价格将股票卖给风险投资公司，力扣希望在 IPO 之前开展一些项目以增加其资本。由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助力扣设计完成最多 k 个不同项目后得到最大总资本的方式。

给你 n 个项目。对于每个项目 i，它都有一个纯利润 profits[i]，和启动该项目需要的最小资本 capital[i]。

最初，你的资本为 w。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

总而言之，从给定项目中选择最多 k 个不同项目的列表，以最大化最终资本，并输出最终可获得的最多资本。

示例：

输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4
解释：
由于你的初始资本为 0，你仅可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。

链接：https://leetcode-cn.com/problems/ipo/ (opens new window)

# 答案

这里使用 java 代码编写，原因是 js 没有 PriorityQueue 这类数据结构，使用排序的话时间复杂度高，再加上 js 性能本来就不行，在 leetcode 上直接超时了。。

分析：由于每完成一个任务都会使得总资金 w 增加或不变。因此对于所选的第 i 个任务而言，应该在所有「未被选择」且启动资金不超过 w 的所有任务里面选利润最大的。因此每次决策前，将启动资金不超过当前总资金的任务加入集合，再在里面取出利润最大的任务，与我们当前的总资金 w 相加，循环求解 k 次即为答案。

class Solution {
  public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
    int n = profits.length;
    // 构建和排序启动资金和利润的二维数组，并排序，时间复杂度为 O(nlogn)
    List<int[]> list = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      list.add(new int[]{ capital[i], profits[i] });
    }
    Collections.sort(list, (a, b) -> a[0] - b[0]);
    // 构建优先级队列（大根堆），poll 操作的时间复杂度为 O(logn)
    PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
    // 由于之前 list 根据启动资金排序过，这里只需要遍历到不符合为止，不需要每次从头到尾遍历
    int i = 0;
    while (k-- > 0) {
      while (i < n && list.get(i)[0] <= w) {
        q.add(list.get(i)[1]);
        i++;
      }
      if (q.isEmpty()) break;
      w += q.poll();
    }
    return w;
  }
}

# 503.下一个更大元素

# 题目

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例：

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

链接：https://leetcode-cn.com/problems/next-greater-element-ii/ (opens new window)

# 答案

刚接触这道题的时候直接使用双 for 循环暴力破解，结果太费时间了。。现在考虑优化的情况，我们注意到，暴力解法中，如果数组的前半部分是单调不增的，那么会有很大的计算资源的浪费。比如说 [6,5,4,3,8]，对于前面的 [6,5,4,3] 等数字都需要向后遍历，当寻找到元素 8 时才找到了比自己大的元素；而如果已知元素 6 向后找到元素 8 才找到了比自己的大的数字，那么对于元素 [5,4,3] 来说，它们都比元素 6 更小，所以比它们更大的元素一定是元素 8，不需要单独遍历对 [5,4,3] 向后遍历一次。

根据上面的分析可知，可以遍历一次数组，如果元素是单调递减的（则他们的「下一个更大元素」相同），我们就把这些元素保存，直到找到一个较大的元素；把该较大元素逐一跟保存了的元素比较，如果该元素更大，那么它就是前面元素的「下一个更大元素」，在实现上，我们可以使用「单调栈」来实现。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var nextGreaterElements = function(nums) {
  const n = nums.length;
  const res = new Array(n).fill(-1);
  // 用一个栈保存值递减的下标（单调递减栈）
  const stk = [];

  for (let i = 0; i < n * 2 - 1; i++) {
    // 检查栈顶对应值与当前值
    // 如果大于则不处理，后续执行 push 后保持单调递减的特性
    // 如果小于则需要循环处理单调栈，直到栈顶对应值大于当前值，那么处理前的栈顶到处理后的栈顶的最近最大值即为当前值
    while (stk.length && nums[stk[stk.length - 1]] < nums[i % n]) {
      res[stk[stk.length - 1]] = nums[i % n];
      stk.pop();
    }
    stk.push(i % n);
  }

  return res;
};

← 简介树 →