题目详情

数组arr是[0, 1, …, arr.length - 1]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

我们最多能将数组分成多少块？

示例 1:

输入: arr = [4,3,2,1,0]

输出: 1

解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。

输入: arr = [1,0,2,3,4]

输出: 4

解释:

我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。

然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。

思路

  • indexSum记录当前遍历的最大索引值
  • sum是当前和
  • count是块数
  • 遍历过程中如果索引值的和 和 sum 不相等那就跳过继续循环直到相等了这一”分区”必然能排列成正确数列

具体代码

  1. /**
  2.  * @param {number[]} arr
  3.  * @return {number}
  4.  */
  5. var maxChunksToSorted = function(arr) {
  6.     let indexSum = sum = count = 0
  7.     for(let i = 0, len = arr.length; i < len; i++) {
  8.         sum += arr[i]
  9.         indexSum += i
  10.         if(sum === indexSum) count++
  11.     }
  12.     return count
  13. };

Array - 714. 买卖股票的最佳时机含手续费（重点）

之前在《JavaScript数据结构和算法》上也有过示例，然后我也理所当然的忘了。 QAQ

题目详情

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每次交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

示例:

输入: prices = [1, 3, 2, 8, 4, 9], fee = 2

输出: 8

解释:
能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

思路

  • DP
  • 遍历过程算出每个i的最大利润值，最小买入值
  • 最小买入值=Math.min(上一次买入, 当前总买入值)
  • 最大利润=Math.max(上一次利润, 当前利润)

具体代码

/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {
    let n = prices.length;
    let hold = prices[0],
        sold = 0;
    for (let i = 1; i < n; ++i) {
        hold = Math.min(hold, prices[i] - sold);
        sold = Math.max(sold, prices[i] - hold - fee);
    }
    return sold;
};