跳到主要内容

分治

分治算法​

基本思路​

  • 分：递归将原问题分为多个子问题，直至达到最小子问题；
  • 治：从最小子问题，从下而上合并，构建原问题解；

分治前提​

  • 问题可以分解；
  • 子问题独立；
  • 子问题解可以合并；

分治和递归​

  • 分治根据实现方式的不同；
  • 分为递归和迭代；

常见应用​

  • 大数乘法；
  • 矩阵乘法；
  • 汉诺塔问题；
  • 二分查找；
  • 归并/快速/桶排序；
  • dfs；

基本模板​

def divide_and_conquer(problems_n):             # problems_n 为问题规模
    if problems_n < d:                          # 当问题规模足够小时, 直接解决该问题
        return solove()                         # 直接求解

    problems_k = divide(problems_n)             # 将问题分解为 k 个相同形式的子问题

    res = [0 for _ in range(k)]                 # res 用来保存 k 个子问题的解
    for problem_k in problems_k:
        res[i] = divide_and_conquer(problem_k)  # 递归的求解 k 个子问题

    ans = merge(res)                            # 合并 k 个子问题的解
    return ans                                  # 返回原问题的解

分治题目​

汉诺塔问题​

题目​
思路​
  • 假设 n 个圆盘；
  • 将顶部 n - 1 个圆盘看作一个整体；
  • 分治步骤；
    • C 为缓冲柱，将 n-1 从 A 移至 B；
    • 将 A 剩余的 1 从 A 移至 C；
    • A 为缓冲柱，将 n-1 从 B 移至 C；
  • 终止条件；
    • 当 A 只剩 1 个时，直接从 A 移至 C；
  • 将 f(n) 问题转换为 2 个 f(n-1) 和 1 个 f(1)；
/**
 * @param {number[]} A
 * @param {number[]} B
 * @param {number[]} C
 * @return {void} Do not return anything, modify C in-place instead.
 */
var hanota = function (A, B, C) {
  const dfs = (n, A, B, C) => {
    if (n === 1) {
      C.push(A.pop());
      return;
    }
    dfs(n - 1, A, C, B);
    C.push(A.pop());
    dfs(n - 1, B, A, C);
  };

  dfs(A.length, A, B, C);
};

合并 k 个链表​

题目​
思路​
  • 等同于链表的归并排序；
  • 将单一链表中点的划分，替换为链表数组的划分；
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
  const merge = (l1, l2) => {
    const dummy = new ListNode(-1);
    let cur = dummy;
    while (l1 != null && l2 != null) {
      if (l1.val < l2.val) {
        cur.next = l1;
        l1 = l1.next;
      } else {
        cur.next = l2;
        l2 = l2.next;
      }
      cur = cur.next;
    }
    if (l1) cur.next = l1;
    if (l2) cur.next = l2;

    return dummy.next;
  };

  const mergeK = (lists, left, right) => {
    if (left >= right) return lists[left];
    const mid = Math.floor(left + (right - left) / 2);
    const l1 = mergeK(lists, left, mid);
    const l2 = mergeK(lists, mid + 1, right);
    return merge(l1, l2);
  };

  if (lists.length === 0) return null;
  return mergeK(lists, 0, lists.length - 1);
};
复杂度​
  • 时间：；
  • 空间：；

寻找两个正序数组的中位数​

题目​
  • 4；
思路​
  • 当数组长度之和为奇数时，中位数为数组第 Math.floor((m + n)/2) + 1 个元素；
  • 反之为数组第 Math.floor((m + n)/2) 个元素和数组第 Math.floor((m + n)/2) + 1 个元素的平均数；
  • 所以包含中位数的数组一侧个数恒为 Math.floor((m + n + 1)/2)，记作 k；
  • 此时问题变为如何在两数组中取前 k 小的元素位置；
    • nums1 取 a 个，nums2 取 k - a 个；
    • 取较短元素设置为 nums1；
    • 设置两端指针 left，right 指向 nums1 两端；
    • 取中间位置 mid，作为 a；
    • 比较 nums1[a] 和 nums2[k-a-1]；
      • 如果 nums1[a] < nums2[k-a-1]；
        • 说明最多有 a + k - a - 1 = k - 1 个元素比 nums1[a] 小；
        • 故 nums1[a-1] 不可能是第 k 个元素；
        • left = mid + 1；
      • 反之，right = mid；
  • 此时，可能存在的中位数对应 num1[left-1] 和 nums[k-left-1]，需要判断两者是否存在；
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  if (nums1.length > nums2.length) {
    return findMedianSortedArrays(nums2, nums1);
  }
  const k = Math.floor((nums1.length + nums2.length + 1) / 2);
  let left = 0;
  let right = nums1.length;
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums1[mid] < nums2[k - mid - 1]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  const n = left;
  const m = k - left;
  const v1 = Math.max(
    n <= 0 ? -Infinity : nums1[n - 1],
    m <= 0 ? -Infinity : nums2[m - 1]
  );
  if ((nums1.length + nums2.length) % 2 === 1) return v1;
  const v2 = Math.min(
    n >= nums1.length ? Infinity : nums1[n],
    m >= nums2.length ? Infinity : nums2[m]
  );
  return (v1 + v2) / 2;
};
复杂度​
  • 时间：log(m+n)；
  • 空间：1；

Pow(x,n)​

题目​
思路​
  • 快速幂算法；
    • 如果 n 为偶数，xn=(x2)n//2x^n=(x^2)^{n//2}；
    • 反之，xn=x(x2)n//2x^n=x(x^2)^{n//2}；
  • 基于分治的思想，复杂度降低为 logn；
/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function (x, n) {
  if (n < 0) return myPow(1 / x, -n);
  if (n === 0) return 1;
  if (n % 2 !== 1) return myPow(x * x, Math.floor(n / 2));
  else return x * myPow(x * x, Math.floor(n / 2));
};
复杂度​
  • 时间：logn；
  • 空间：1；

验证二叉搜索树的后序遍历序列​

题目​
思路​
  • 后序遍历顺序为 "左右根"；
  • 将数组最右侧元素左右根节点值，判断数组左右两者是否符合左侧都小于，右侧都大于；
    • 若满足，找到左右分界线位置，递归子数组；
    • 若不满足，说明不是二叉搜索树的后序遍历结果；
  • 终止条件：left>=right，说明当前只有一个节点；
/**
 * @param {number[]} postorder
 * @return {boolean}
 */
var verifyTreeOrder = function (postorder) {
  const dfs = (left, right) => {
    if (left >= right) return true;
    let index = left;
    while (postorder[index] < postorder[right]) index++;
    const mid = index;
    while (postorder[index] > postorder[right]) index++;

    return index === right && dfs(left, mid - 1) && dfs(mid, right - 1);
  };

  return dfs(0, postorder.length - 1);
};
复杂度​
  • 时间：n^2；
  • 空间：n；

回溯算法​

基本思想​
  • 基于穷举和深度优先遍历解决问题；
  • 从某个初始状态出发，穷举所有可能，直至找到解或无解；
尝试和回退​
  • 当搜索过程中，状态无法继续前进；
  • 撤销上一步选择，回退到之前状态，尝试其他可能；
剪枝​
  • 根据回溯问题的约束条件；
  • 避免无意义的搜索路径；
模板代码​
  • 定义决策树；
  • 明确终止条件；
  • 翻译代码；
    • 定义回溯函数；
    • 回溯函数主体；
      • 剪枝；
      • 选择元素；
      • 递归搜索；
      • 回退；
    • 明确终止条件；
/* 回溯算法框架 */
function backtrack(state, choices, res) {
  // 判断是否为解
  if (isSolution(state)) {
    // 记录解
    recordSolution(state, res);
    // 不再继续搜索
    return;
  }
  // 遍历所有选择
  for (let choice of choices) {
    // 剪枝: 判断选择是否合法
    if (isValid(state, choice)) {
      // 尝试: 做出选择, 更新状态
      makeChoice(state, choice);
      // 递归搜索
      backtrack(state, choices, res);
      // 回退: 撤销选择, 恢复到之前的状态
      undoChoice(state, choice);
    }
  }
}

回溯算法题目​

子集​

题目​
思路​
  • 对于每个元素，都有选与不选两个选择；
  • 遍历数组；
    • 当前元素索引为 cur，遍历 nums[cur+1：-1]，避免选取重复元素；
    • 添加当前路径到 res；
    • 逐个假设其被选择，递归选择元素，其为下一次递归的当前元素；
    • 直至到达数组末尾；
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
  const backtrack = (res, state, index, nums) => {
    res.push([...state]);
    if (index === nums.length) {
      return;
    }
    for (let i = index; i < nums.length; i++) {
      state.push(nums[i]);
      backtrack(res, state, i + 1, nums);
      state.pop();
    }
  };

  const res = [];
  backtrack(res, [], 0, nums);

  return res;
};
复杂度​
  • 时间：n*2^n；
  • 空间：n；

n 皇后​

题目​
思路​
  • 每一行只能放置一个皇后；
    • 遍历数组一维索引，逐索引放置；
  • 约束条件；
    • 每一列只能放置一个皇后；
      • 定义长度为 n 的布尔数组 cols，记录每一列是否有皇后；
    • 同一对角线只能放置一个皇后；
      • 主对角线上的格子 row - col 为恒定值，范围为 [-n+1，n-1]；
      • 次对角线上的格子 row + col 为恒定值，范围为 [0，2n-2]；
      • 定义 diags 数组，记录对角线上是否有皇后；
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
  const dfs = (row, n, state, res, cols, diags1, diags2) => {
    if (row >= n) {
      res.push(state.map((row) => row.join("")));
      return;
    }
    for (let col = 0; col < n; col++) {
      const diag1 = row - col + n - 1;
      const diag2 = row + col;
      if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
        state[row][col] = "Q";
        cols[col] = diags1[diag1] = diags2[diag2] = true;
        dfs(row + 1, n, state, res, cols, diags1, diags2);
        state[row][col] = ".";
        cols[col] = diags1[diag1] = diags2[diag2] = false;
      }
    }
  };

  const state = Array.from({ length: n }, () => Array(n).fill("."));
  const cols = Array(n).fill(false);
  const diags1 = Array(2 * n - 1).fill(false);
  const diags2 = Array(2 * n - 1).fill(false);
  const res = [];

  dfs(0, n, state, res, cols, diags1, diags2);
  return res;
};
复杂度​
  • 空间：n!；
  • 时间：n^2；

全排列 1​

题目​
思路​
  • 引入布尔数组 selected，selected[i] 记录 nums[i] 是否被选择；
  • 作出选择后，将对应 selected[i] 赋值为 True；
  • 遍历选择时，跳过所有为 True 的 selected，即剪枝；
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const backtrack = (res, state, selected, nums) => {
    if (state.length === nums.length) {
      res.push([...state]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (selected[i]) continue;
      selected[i] = true;
      state.push(nums[i]);
      backtrack(res, state, selected, nums);
      selected[i] = false;
      state.pop();
    }
  };

  const res = [];
  const selected = new Array(nums.length).fill(false);
  backtrack(res, [], selected, nums);

  return res;
};
复杂度​
  • 时间：n*n!；
  • 空间：n；

全排列 2​

题目​
思路​
  • 在全排列的基础上；
  • 判断其上一个元素是否相等且是否访问；
    • 如果相等且未被访问，跳过；
    • 若存在相邻的两个重复元素；
      • 存在 AB 和 BA 两种顺序，两者相同；
      • 所以使用 !selected[i - 1] 筛选出其中一种情况，加不加 ! 都可以；
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  const backtrack = (res, state, selected, nums) => {
    if (state.length >= nums.length) {
      res.push([...state]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (i >= 1 && nums[i] === nums[i - 1] && !selected[i - 1]) continue;
      if (selected[i]) continue;
      state.push(nums[i]);
      selected[i] = true;
      backtrack(res, state, selected, nums);
      state.pop();
      selected[i] = false;
    }
  };

  const res = [];
  const selected = new Array(nums.length).fill(false);
  backtrack(
    res,
    [],
    selected,
    nums.sort((a, b) => a - b)
  );

  return res;
};
复杂度​
  • 时间：n*n!；
  • 空间：n；

组合总和 1​

题目​
思路​
  • 通过 target-=nums[i]，少定义 sum，也可是不使用，看你心情；
  • 首先对 nums 进行排序，当 target < 0 或 target > sum 直接结束循环；
  • 明确所有选择：对剩余元素进行遍历；
  • 明确终止条件：target === 0/sum 或到达数组末端；
  • 定义回溯函数：backtrack(res，state，index，target，nums)；
    • 遍历 [index，-1]，避免重复组合的生成，实现同一元素的重复选取；
    • target < 0 为剪枝条件；
  • 终止条件；
    • 终止条件：sum > target；
    • 更新结果：target === 0/sum；
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
  const backtrack = (res, state, index, sum, target, nums) => {
    if (sum > target) return;
    if (sum === target) {
      res.push([...state]);
      return;
    }

    for (let i = index; i < nums.length; i++) {
      sum += nums[i];
      if (sum > target) break;
      state.push(nums[i]);
      backtrack(res, state, i, sum, target, nums);
      state.pop();
      sum -= nums[i];
    }
  };

  const res = [];
  candidates.sort((a, b) => a - b);
  backtrack(res, [], 0, 0, target, candidates);

  return res;
};
复杂度​
  • 时间：n * 2^n；
  • 空间：n；

组合总和 2​

题目​
思路​
  • 在组合总和 1 的基础上，增加剪枝条件；
    • 索引从 i+1 开始，避免同一元素的重复选取；
    • 遍历 index 时，判断与上一个元素是否相同，相同则跳过，避免重复组合的生成；
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
  const backtrack = (res, state, index, sum, target, nums) => {
    if (sum > target) return;
    if (sum === target) {
      res.push([...state]);
      return;
    }

    for (let i = index; i < nums.length; i++) {
      if (sum + nums[i] > target) break;
      if (i > index && nums[i - 1] === nums[i]) continue;
      state.push(nums[i]);
      sum += nums[i];
      backtrack(res, state, i + 1, sum, target, nums);
      state.pop();
      sum -= nums[i];
    }
  };

  const res = [];
  candidates.sort((a, b) => a - b);
  backtrack(res, [], 0, 0, target, candidates);

  return res;
};
复杂度​
  • 时间：n * 2^n；
  • 空间：n；

括号生成​

题目​
思路​
  • 一共 2 * n 个括号；
  • 明确所有选择：添加 ( 或 )；
  • 明确终止条件：添加 2 * n 个括号；
  • 定义回溯函数：backtrack(state，res，n，symbol)；
    • 剪枝；
      • 使用 symbol 表示当前组合是否成对匹配；
        • 添加 (，symbol+=1；
        • 添加 )，symbol-=1；
        • 只有 symbol < n，才可添加 (；
        • 只有 symbol > 0，才可添加 )；
  • 终止条件；
    • 终止条件：state.length === 2 * n；
    • 添加结果：终止条件且 symbol === 0；
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  const backtrack = (res, state, tag, n) => {
    if (state.length === 2 * n) {
      if (tag === 0) res.push(state.join(""));
      return;
    }
    if (tag > 0) {
      state.push(")");
      backtrack(res, state, tag - 1, n);
      state.pop();
    }
    if (tag < n) {
      state.push("(");
      backtrack(res, state, tag + 1, n);
      state.pop();
    }
  };

  const res = [];
  backtrack(res, [], 0, n);
  return res;
};
复杂度​
  • 时间：22×nn\frac{2^{2 \times n}}{\sqrt{n}}；
  • 空间：n；

复原 ip 地址​

题目​
思路​
  • 通过在字符串种添加三个点生成不同 IP 地址；
  • 明确所有选择：每个部分有剩余全部元素给出；
  • 终止条件：分割为 4 部分；
  • 定义回溯函数 trackback(res，state，index，s)；
    • index 为剩余元素的起始索引；
  • 书写回溯函数主体；
    • 剪枝；
      • 从剩余元素选择，即 i in [index：-1]；
      • 判断 s[index：i-1] 的值；
        • > 255：跳过；
        • 存在前导 0，但并非单个零：跳过；
  • 终止条件；
    • 终止条件：路径长度大于 4；
    • 更新状态：路径长度等于 4，且位置处于字符串末端；
/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function (s) {
  const dfs = (res, state, index, s) => {
    if (index >= s.length) {
      if (state.length === 4) res.push(state.join("."));
      return;
    }

    for (let i = index; i < s.length; i++) {
      const sub = s.slice(index, i + 1);
      if (sub[0] === "0" && i !== index) break;
      const num = Number(sub);
      if (sub > 255) break;
      state.push(num);
      dfs(res, state, i + 1, s);
      state.pop();
    }
  };

  const res = [];
  dfs(res, [], 0, s);

  return res;
};
复杂度​
  • 时间：3^4 * |s|；
  • 空间：|s|；

解数独​

题目​
思路​
  • 原理类似 n 皇后；
  • 遍历棋盘格子，对于每个格子，遍历 1- 9，判断同行，同列，9 宫格是否重复；
    • 如果 val 有效，立刻返回 true，如果遍历 1 - 9 均无效，返回 false；
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function (board) {
  const isValid = (row, col, val, board) => {
    for (let i = 0; i < 9; i++) {
      if (val === board[row][i] || val === board[i][col]) return false;
    }

    const startRow = Math.floor(row / 3) * 3;
    const startCol = Math.floor(col / 3) * 3;
    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        if (val === board[startRow + i][startCol + j]) return false;
      }
    }
    return true;
  };

  const backtrack = (board) => {
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        if (board[i][j] !== ".") continue;
        for (let k = 1; k < 10; k++) {
          if (!isValid(i, j, String(k), board)) continue;
          board[i][j] = String(k);
          const res = backtrack(board);
          if (res === true) return true;
          board[i][j] = ".";
        }
        return false;
      }
    }
    return true;
  };

  backtrack(board);
};
复杂度​
  • 时间：9^m；
  • 空间：9^2；

单词搜索​

题目​
思路​
  • 明确所有选择：向四个方向移动；
  • 确定终止条件：单词不匹配或者遍历完单词；
  • 确定递归函数：backtrack(col，row，visited，wordIndex，word)；
    • 判断当前矩阵元素是否匹配单词当前字符；
    • 定义已访问节点 visited；
    • 遍历四个方向；
    • 剪枝；
      • 超过矩阵索引范围；
      • 当前节点已经被访问；
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  const dirctionList = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  const rows = board.length;
  const cols = board[0].length;

  const backtrack = (row, col, visited, index, word, board) => {
    if (index === word.length - 1) return word[index] === board[row][col];

    if (word[index] === board[row][col]) {
      visited[row][col] = true;
      for (const [dx, dy] of dirctionList) {
        const curCol = col + dx;
        const curRow = row + dy;
        if (
          curCol < 0 ||
          curCol >= cols ||
          curRow < 0 ||
          curRow >= rows ||
          visited[curRow][curCol]
        )
          continue;
        const res = backtrack(curRow, curCol, visited, index + 1, word, board);
        if (res) return true;
      }
      visited[row][col] = false;
    }

    return false;
  };

  const visited = Array.from(
    {
      length: rows,
    },
    () => new Array(cols).fill(false)
  );
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      const res = backtrack(i, j, visited, 0, word, board);
      if (res) return true;
    }
  }

  return false;
};
复杂度​
  • 时间：mn*2^l；
  • 空间：mn；

贪心算法​

概述​

  • 分步解决算法；
  • 解决问题的每个决策阶段，选择当前的最优解；
  • 贪心作出局部最优，期望获得全局最优；

特征​

  • 贪心选择性质：全局最优解可通过局部最优解得到；
  • 最优子结构：问题最优解包括子问题最优解；

解题思路​

  • 转换为贪心问题：作出当前选择，再解决剩余子问题；；
  • 贪心选择性质：选择当前最优解；
  • 最优子结构性质：根据局部最优解构造全局最优解；

贪心题目​

买卖股票的最佳时机 1​

题目​
思路​
  • 贪心问题：递推得到当天的最低成本和最大利润；
  • 贪心选择性质；
    • 对当天价格进行比较，更新最低成本；
    • 计算当天的最大理论
  • 最优子结构：全局最大利润；
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let min = prices[0];
  let max = 0;

  for (let i = 1; i < prices.length; i++) {
    min = Math.min(min, prices[i]);
    max = Math.max(max, prices[i] - min);
  }

  return max;
};
复杂度​
  • 时间：n；
  • 空间：1；

买卖股票的最佳时机 2​

题目​
思路​
  • 贪心问题：决定当天是否买卖股票，然后进行下一次选择；
  • 贪心选择性质；
    • 赚钱就买卖，反之不买卖；
    • 即判断当天和前一天的差值；
  • 最优子结构；
    • 利润累加；
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let res = 0;
  for (let i = 1; i < prices.length; i++) {
    res += Math.max(0, prices[i] - prices[i - 1]);
  }
  return res;
};
复杂度​
  • 时间：n；
  • 空间：1；

跳跃游戏 2​

题目​
思路​
  • 贪心问题：根据当前可以到达的最大位置，判断当前位置，是否更新最小方案数 res 和最大位置 pos；
  • 贪心选择性质；
    • 遍历当前位置；
    • 实时维护最大距离 dis；
    • 如果当前位置为最大位置 pos，更新 res 和 pos；
  • 最优子结构；
    • 返回 res；
/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function (nums) {
  let res = 0;
  let pos = 0;
  let dis = 0;
  for (let i = 0; i < nums.length; i++) {
    if (pos >= nums.length - 1) break;
    dis = Math.max(dis, i + nums[i]);
    if (pos === i) {
      pos = dis;
      res++;
    }
  }

  return res;
};
复杂度​
  • 时间：n；
  • 空间：1；

移掉 k 位数字​

题目​
思路​
  • 基于单调栈和贪心；
  • 贪心问题：结果更有 n-k 位，希望高位数字越小越好；
  • 贪心选择性质；
    • 使用最小栈遍历数组，保证高位数字最小；
    • 如果遍历数组后，仍未移除 k 个，手动移除栈顶元素至 k 个；
    • 注意处理前导 0；
  • 最优子结构；
    • 返回 stack，如果栈为空返回 0；
/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
var removeKdigits = function (num, k) {
  const minStack = [];
  for (const ch of num) {
    while (
      k > 0 &&
      minStack.length !== 0 &&
      ch < minStack[minStack.length - 1]
    ) {
      minStack.pop();
      k--;
    }
    if (ch !== "0" || minStack.length !== 0) minStack.push(ch);
  }

  while (k > 0) {
    minStack.pop();
    k--;
  }

  return minStack.length === 0 ? "0" : minStack.join("");
};
复杂度​
  • 时间：n；
  • 空间：n；

分发糖果​

题目​
思路​
  • 贪心问题；
    • 每个孩子至少有一个，即糖果数目至少为 n；
    • 分高孩子比两侧孩子糖果多；
      • ratings[i-1] < ratings[i]，res[i-1] < res[i]；
      • ratings[i] > ratings[i+1]，res[i] > res[i+1]；
  • 贪心选择性质；
    • 定义长度为 n 的数组，初始化为 1；
    • 遍历两次数组，分别满足两侧大小的对应条件；
      • 正序遍历，满足左规则：ratings[i-1] < ratings[i]，res[i]=res[i-1]+1；
      • 倒序遍历，满足右规则：ratings[i] > ratings[i+1]，res[i]=max(res[i]，res[i+1]+1)；
        • 和右侧进行比较，所有优先计算右侧，故倒序遍历；
  • 最优子结构；
    • 返回 res 的总和；
/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function (ratings) {
  const n = ratings.length;
  const res = new Array(n).fill(1);

  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) res[i] = res[i - 1] + 1;
  }
  for (let i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) res[i] = Math.max(res[i], res[i + 1] + 1);
  }

  return res.reduce((a, b) => a + b, 0);
};
复杂度​
  • 时间：n；
  • 空间：n；

加油站​

题目​
思路​
  • 计算所有加油站能够提供的油量和汽车消耗量；
    • 如果油量大于消耗量，必能行驶一周；
      • 可以将加油和消耗看作 [+，-，。。。，+，+] 的数组；
      • 如果 + 对应数值总和大于 - 对应数值总和；
      • 总能找到多个子数组的组合，使得每个子数组总和都大于 0；
  • 不考虑油量为负的情况，从 start 出发，计算两者差值 diff 和汽车剩余油量 min；
  • 如果 min<0，则说明不能 start 在出发环行一周，start = i+1，min = 0；
  • 如果 diff < 0 必不能环形一周；
  • 反之返回 start；
/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
var canCompleteCircuit = function (gas, cost) {
  let diff = 0;
  let min = 0;
  let start = 0;
  for (let i = 0; i < gas.length; i++) {
    diff += gas[i] - cost[i];
    min += gas[i] - cost[i];
    if (min < 0) {
      start = i + 1;
      min = 0;
    }
  }
  if (diff < 0) return -1;
  return start;
};
复杂度​
  • 时间：；
  • 空间：；