# LeetCode 1005. K 次取反后最大化的数组和

1005. Maximize Sum Of Array After K Negations

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

示例 1：

输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3]

示例 2：

输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2]

示例 3：

输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4]

提示：

$1 \le$ nums.length $\le 10^4$
$-100 \le$ nums[i] $\le 100$
$1 \le $ k $\le 10^4$

# 思路

为使得数组和最大，每次的取反操作应尽可能针对负数进行，并且，应优先将值最小的负数取反（以获得值较大的正数）

特别地，如果 K 大于数组中负数的个数，意味着我们在将所有负数取反之后，必须继续进行取反操作，此时有两种情况：

如果剩余修改次数为偶数，可将这些修改施加于任意一个数，并不会影响数组和
如果剩余修改次数为奇数，应将这些修改施加于值最小的非负数，以使得数组和最大

注意，在将负数修改为正数的过程中，可能产生了新的、值更小的非负数（相比于原数组而言）

# Method: 贪心

贪心策略：

局部最优：将绝对值大的负数修改为正数，使得当前元素值最大
整体最优：整个数组的和最大（数组中的负数和最小）

算法思路：

将数组 按照绝对值的大小从大到小排序
从左往右遍历 数组，在修改次数限制下，将遇到的每一个负数修改为相反数，并更新剩余修改次数（即，执行 k-- ）
如果剩余修改次数为奇数，将绝对值最小的数修改为相反数
计算数组和

代码实现：

class Solution {

static bool cmp(int a, int b) {
    return abs(a) > abs(b);
}

public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), cmp);    // 按照绝对值从大到小进行排序
        for (int i = 0; i < nums.size(); i++) { // 在修改次数限制下，将绝对值大的负数修改为相反数
            if (nums[i] < 0 && k > 0) {
                nums[i] = - nums[i];
                k--;
            }
        }
        if (k % 2 == 1) nums[nums.size() - 1] = - nums[nums.size() - 1]; // 将绝对值最小的数修改为相反数
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            ans += nums[i];
        }
        return ans;
    }
};

时间复杂度： $O(n)$ ，其中 $n$ 为数组长度

排序的时间复杂度为 $O(n \log{n})$ ，这里不予考虑
修改数组、计算数组和的时间复杂度均为 $O(n)$

空间复杂度： $O(1)$

参考：代码随想录

# LeetCode 122. 买卖股票的最佳时机 II

122. Best Time to Buy and Sell Stock II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和 / 或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在 同一天 出售。

返回你能获得的最大利润。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。总利润为 4 + 3 = 7 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

提示：

$1 \le$ prices.length $\le 3 \times 10^4$
$0 \le$ prices[i] $\le 10^4$

# 思路

LeetCode 121. 买卖股票的最佳时机 只能进行一次交易，而本题可以进行多次交易

在某种程度上，可以理解为：两题都可以进行多次交易，但 LeetCode 121. 买卖股票的最佳时机 求的是所有交易中的最大收益，本题求的是所有交易的收益和（正收益之和）

# Method 1: 贪心

贪心策略：每天至多持有一只股票，要想获得最大利润，则需低点买入、高点卖出：即，在第一个「谷」买入，在第一个「峰」卖出，然后在下一个「谷」买入，再在下一个「峰」卖出，以此往复

算法思路：按天计算利润，仅收集每天的正利润，以获得最大利润（该过程并未模拟股票交易过程）

详细说明可参考力扣官方题解：买卖股票的最佳时机 II

代码实现：

int maxProfit(vector<int>& prices) {
    int result = 0;
    for (int i = 1; i < prices.size(); i++) { // 只记录每天的正收益
        result += max(prices[i] - prices[i - 1], 0);
    }
    return result;
}

时间复杂度： $O(n)$ ，其中 $n$ 是数组 prices 的长度

空间复杂度： $O(1)$

# Method 2: 动态规划

算法思路：

定义 dp 数组： vector<vector<int>> dp(n, vector<int>(2,0))

dp[i][0] 表示第 i 天持有股票时的最大利润
dp[i][1] 表示第 i 天不持有股票时的最大利润

确定递推公式：

第 i 天持有股票，即， dp[i][0]
- 若第 i - 1 天持有股票，则最大利润为 dp[i - 1][0]
- 若第 i - 1 天不持有股票，即，第 i 天买入股票，则最大利润为 dp[i - 1][1] - prices[i] （虽然第 i - 1 天不持有股票，但此前可能进行过完整交易，因此，第 i 天的利润应为 dp[i - 1][1] 减去 prices[i] ，而这也就是与 LeetCode 121. 买卖股票的最佳时机 的差异所在）
- 综合两种情况得 dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
第 i 天不持有股票，即， dp[i][1]
- 若第 i - 1 天持有股票，即，第 i 天卖出股票，则最大利润为 dp[i - 1][0] + prices[i]
- 若第 i - 1 天不持有股票，则最大利润为 dp[i - 1][1]
- 综合两种情况得 dp[i][1] = max(dp[i - 1][0] + prices[i], dp[i - 1][1])

初始化 dp 数组：

若第 0 天持有股票，当前利润应为 - prices[0] ，即 dp[0][0] = - prices[0]
若第 0 天不持有股票，利润为 0 ，即 dp[i][1] = 0

遍历顺序：按 i 从小到大遍历

最后的 dp[n - 1][1] 即为所求

代码实现：

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<vector<int>> dp(n, vector<int>(2,0));
    dp[0][0] = - prices[0];
    dp[0][1] = 0;
    for (int i = 1; i < n; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
        dp[i][1] = max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
    }
    return dp[n - 1][1];
}

时间复杂度： $O(n)$ ，其中 $n$ 是数组 prices 的长度

空间复杂度： $O(n)$

可以采用滚动数组优化空间复杂度

# LeetCode 134. 加油站

134. Gas Station

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯一的。

示例 1：

输入：gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出：3
解释：
    从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
    开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
    开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
    开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
    开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
    开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
    因此，3 可为起始索引。

示例 2：

输入：gas = [2,3,4], cost = [3,4,3]
输出：-1
解释：
    你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
    我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
    开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
    开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
    你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
    因此，无论怎样，你都不可能绕环路行驶一周。

提示：

n == gas.length == cost.length
$1 \le$ n $\le 10^5$
$0 \le$ gas[i] , cost[i] $\le 10^4$

# 思路

如果从站点 $i$ 出发，最远能到达站点 $j$ ，则：从 $[i, j]$ 区间内任意一个站点出发，都无法回到该站点

证明如下：假设可以从 $k \in [i, j]$ 出发并回到 $k$ ，此时， $k$ 必然能够到达 $j + 1$ ；由于 $i$ 能够到达 $k$ ，则 $i$ 能够到达 $j + 1$ ，与已知条件矛盾，故而无法从 $k$ 出发并回到 $k$

即，如果存在一个可行的出发站点，则必然是 $j + 1$ 及其以后站点中的某一个

参考：windliang：详细通俗的思路分析

# Method 1

算法思路：首先检查站点 i = 0 是否为可行的出发站点：如果不是，记录其能到达的最远站点，将其更新为 i ，检查新的 i 是否为可行的出发站点

代码实现：

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int n = gas.size();
    int i = 0;
    while (i < n) {     // 判断 i 是否为可行的出发站点
        int sumGas = 0, sumCost = 0;
        int cnt = 0;    // 从 i 出发时，所能经过的站点数
        while (cnt < n) {
            int j = (i + cnt) % n;
            sumGas += gas[j];
            sumCost += cost[j];
            if (sumCost > sumGas) break; // 无法到达第 j + 1 个站点
            cnt++;
        }
        if (cnt == n) { // 从 i 出发，能经过 n 个站点，i 即为所求 
            return i;
        } else {        // [i, i + cnt] 区间内任一站点都不是可行的出发站点
            i = i + cnt + 1;
        }
    }
    return -1;
}

时间复杂度： $O(n)$ ，其中 $n$ 是数组长度

空间复杂度： $O(1)$

参考：力扣官方题解

# Method 2

算法思路：

定义 totalSum ，用于累计每个站点的剩余油量，以判断是否存在一个可行的出发站点
定义 curSum ，用于累计从某个站点出发至今的剩余油量（最初从站点 0 开始累计）
定义 start ，作为当前考虑的出发站点
从左往右遍历站点 i
- 计算 totalSum = totalSum + gas[i] - cost[i]
- 计算 curSum = curSum + gas[i] - cost[i]
- 判断 curSum 是否小于 0
  - 若不小于 0 ，说明从 start 出发能到达站点 i + 1 ，继续遍历
  - 若小于 0 ，说明从 start 出发最远只能到达站点 i ，而不能到达站点 i + 1
    - 更新 start 为 i + 1 ，判断 i + 1 是否为可行的出发点
    - 重置 curSum ，累计从站点 i + 1 出发的剩余油量
遍历结束，判断 totalSum 是否小于 0
- 若小于 0 ，说明 gas 之和小于 cost 之和，不存在可行的出发站点，返回 -1
- 若不小于 0 ，说明存在一个可行的出发站点，并且，该出发站点即为 start

代码实现：

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int start = 0;
    int curSum = 0;        // 从 start 出发，当前的剩余油量
    int totalSum = 0;      // 累计 gas 与 cost 的差值
    for (int i = 0; i < gas.size(); i++) {
        curSum += gas[i] - cost[i];
        totalSum += gas[i] - cost[i];
        if (curSum < 0) {  // 从 start 出发最多能到达 i ，无法到达 i + 1
            start = i + 1; // 考虑 i + 1 是否能作为出发站点
            curSum = 0;    // 重新累计剩余油量
        }
    }
    if (totalSum < 0) return -1; // gas 总和小于 cost 总和，任一站点出发均无法返回
    return start;
}

时间复杂度： $O(n)$ ，其中 $n$ 是数组长度

空间复杂度： $O(1)$

参考：代码随想录

附：

为什么 “当可行的出发站点存在时， start 就是该可行站点” ？

这是因为，除了遍历过程中的最后一个 start （不妨记作 ans ）以外，其余所有 start 对应的 curSum 均小于 0 ，其累加值 totalSum 也同样小于 0，即：

$\sum_{i = 0}^{ans - 1} {(gas[i] - cost[i])} < 0$

由于存在可行的出发站点，可得

$\sum_{i = 0}^{ans - 1} {(gas[i] - cost[i])} + \sum_{i = ans}^{gas.size() - 1} {(gas[i] - cost[i])} > 0$

即：

$\sum_{i = ans}^{gas.size() - 1} {(gas[i] - cost[i])} > \sum_{i = 0}^{ans - 1} {(cost[i] - gas[i])}$

因此，从 ans 出发到达站点 gas.size() - 1 时，其剩余油量足以继续前往站点 0 , 1 , ..., ans

即， ans 是可行的出发站点

# LeetCode 135. 分发糖果

135. Candy

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。

提示：

n == ratings.length
$1 \le$ n $\le 2 \times 10^4$
$0 \le$ ratings[i] $\le 2 \times 10^4$

# 思路

考虑以下两个规则：

左规则：右边评分大于左边时，右边孩子的糖果应比左边孩子多
右规则：左边评分大于右边时，左边孩子的糖果应比右边孩子多

可以遍历数组两次，分别处理「左规则」和「右规则」，求出每个孩子最少需要被分得的糖果数量，最终每个孩子分得的糖果数量应为两种规则下的最大值

如果两种规则同时考虑，很可能会顾此失彼

# Method: 贪心

算法思路：

定义数组 nums 记录每个孩子应得糖果的数量
处理「左规则」：从左往右遍历（只能是从左往右遍历，因为右边孩子的糖果数需要根据左边孩子糖果数的变化而变化）：
- 若 ratings[i] > ratings[i - 1] ，则 i 应比 i - 1 多得一颗糖果，即 nums[i] = nums[i - 1] + 1
处理「右规则」：从右往左遍历（只能是从右往左遍历，因为左边孩子的糖果数需要根据右边孩子糖果数的变化而变化）
- 若 ratings[i] > ratings[i + 1] ，此时需作以下考虑：
  - 由于 i 的评分高于 i + 1 ，分给 i 的糖果数应至少为 nums[i + 1] + 1
  - 处理完「左规则」后，分给 i 的糖果数应至少为 nums[i]
  - 为确保两种规则同时满足，分给 i 的糖果数应为 nums[i + 1] + 1 与 nums[i] 中的较大值，即 nums[i] = max(nums[i], nums[i + 1] + 1)
计算糖果总数：求数组 nums 的元素和

代码实现：

int candy(vector<int>& ratings) {
    int n = ratings.size();
    vector<int> nums(n, 1);     // 分配给每个孩子的糖果数
    // 处理左规则
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1])
            nums[i] = nums[i - 1] + 1;
    }
    // 处理右规则
    for (int i = n - 1; i >= 1; i--) {
        if (ratings[i - 1] > ratings[i])
            nums[i - 1] = max(nums[i - 1], nums[i] + 1); // 注意这里要取两种规则下的最大值
    }
    int ans = 0; // 最少糖果数目
    for (int i = 0; i < n; i++) {
        ans += nums[i];
    }
    return ans;
}

时间复杂度： $O(n)$ ，其中 $n$ 是数组 ratings 的长度

空间复杂度： $O(n)$

参考：

代码随想录
力扣官方题解

# LeetCode 376. 摆动序列

376. Wiggle Subsequence

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反， [1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1：

输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3)

示例 2：

输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 的摆动序列。其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8)

示例 3：

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

提示：

$1 \le$ nums.length $\le 1000$
$0 \le$ nums[i] $\le 1000$

进阶：你能否用 $O(n)$ 时间复杂度完成此题？

# Method: 贪心

算法思路：不断交错选择数组中的「峰」与「谷」，使得摆动子序列尽可能长

如下图所示，选择 [1, 17, 5, 15, 5, 16, 8] 即可得到最长的摆动子序列（答案不唯一），这也就是贪心策略在本题中的体现

本题要求的是最长摆动子序列的长度，也就是数组中 交替出现 的「峰」与「谷」的数量和，可通过计算 交替出现 的「上升坡」和「下降坡」的数量来获得

若 nums[i] > nums[i - 1] ，则 nums[i - 1] 与 nums[i] 之间形成「上升坡」
若 nums[i] < nums[i - 1] ，则 nums[i - 1] 与 nums[i] 之间形成「下降坡」
若 nums[i] == nums[i - 1] ，则 nums[i - 1] 与 nums[i] 之间不形成坡（或者描述为： nums[i - 1] 与 nums[i] 之间形成「平坡」）

不妨用 res 来记录 交替出现 的「上升坡」和「下降坡」的数量之和（ res 的初始值为 0 ）

如果之前统计到的最后一个坡是「下降坡」，当前遇到的坡为「上升坡」，则将当前「上升坡」统计在内， res 加一
如果之前统计到的最后一个坡是「下降坡」，当前遇到的坡仍为「下降坡」，不满足「上升坡」和「下降坡」交替，故而不统计当前「下降坡」
如果之前统计到的最后一个坡是「上升坡」，当前遇到的坡为「下降坡」，则将当前「下降坡」统计在内， res 加一
如果之前统计到的最后一个坡是「上升坡」，当前遇到的坡仍为「上升坡」，不满足「上升坡」和「下降坡」交替，故而不统计当前「上升坡」

因此，所得到的最长摆动序列的长度为 res + 1

代码实现：

int wiggleMaxLength(vector<int> &nums) {
    int n = nums.size();
    if (n <= 1) return n;
    int preDiff = 0; // 在摆动序列中，最后一对数的差值（统计到的最后一个坡）
    int curDiff = 0; // 在原始序列中，当前遍历到的数字与后一个数的差值（当前遇到的坡）
    int res = 1;
    for (int i = 0; i < n - 1; i++) {
        curDiff = nums[i + 1] - nums[i];
        if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) { // 遇到一个与之前方向相反的坡
            res++;
            preDiff = curDiff;
        }
    }
    return res;
}

其中， preDiff 初始化为 0 ，是为了方便统计 nums 数组中的第一个坡（即，直接将数组中的第一个坡统计在内，不管它是「上升坡」还是「下降坡」）

时间复杂度： $O(n)$ ，其中 $n$ 是数组的长度

空间复杂度： $O(1)$

参考：代码随想录：摆动序列

本题也还可以采用动态规划来求解，具体可参考代码随想录和力扣官方题解

# LeetCode 406. 根据身高重建队列

406. Queue Reconstruction by Height

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [h_i, k_i] 表示第 i 个人的身高为 h_i ，前面正好有 k_i 个身高大于或等于 h_i 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [h_j, k_j] 是队列中第 j 个人的属性（ queue[0] 是排在队列前面的人）。

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
    编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
    编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
    编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
    编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
    编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
    编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
    因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：

输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示：

$1 \le$ people.length $\le 2000$
$0 \le h_i \le 10^6$
$0 \le k_i <$ people.length
题目数据确保队列可以被重建

# Method

算法思路：

类似于 LeetCode 135. 分发糖果 ，有两个维度需要处理，此时，可以先确定其中一个维度，再去确定另一个维度

本题应首先对身高 h 进行排序（将身高作为队列重建的第一依据），然后，针对相同的身高，按 k 进行排序

一般地，涉及数对的排序，可以先根据第一个元素正向排序、再根据第二个元素反向排序，或者，根据第一个元素反向排序、再根据第二个元素正向排序

这里首先按身高 h 从大到小排序，然后针对相同的身高按 k 从小到大排序，即

sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {
    return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
});

以示例 1 为例，排序所得结果：

people = [[7,0], [7,1], [6,1], [5,0], [5,2]，[4,4]]

排序完，可以开始重建队列：将 i 插入到队列的位置 $k_i$ （优先处理 $h_i$ 值较大的 i ）

当我们放入第 $i$ 个人时，只需要将其插入队列中，使得他的前面恰好有 $k_i$ 个人即可。这是因为后面的第 $i + 1$ , $\cdots$ , $n - 1$ 个人不会对第 $i$ 个人造成影响（他们都比第 $i$ 个人矮）

插入的过程：

ans = [[7,0]]
ans = [[7,0],[7,1]]
ans = [[7,0],[6,1],[7,1]]
ans = [[5,0],[7,0],[6,1],[7,1]]
ans = [[5,0],[7,0],[5,2],[6,1],[7,1]]
ans = [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

代码实现：

static bool cmp(const vector<int>& a, const vector<int>& b) { // sort 的比较函数
    if (a[0] == b[0]) return a[1] < b[1];
    return a[0] > b[0];
}

vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    sort(people.begin(), people.end(), cmp);  // 排序
    vector<vector<int>> ans;
    for (int i = 0; i < people.size(); i++) { // 重建队列
        vector<int> person = people[i];
        ans.insert(ans.begin() + person[1], person); // 将 person 插入到 person[i] 位置
    }
    return ans;
}

时间复杂度： $O(n^2)$ ，其中 $n$ 是数组的长度

排序的时间复杂度为 $O(n \log{n})$
重建队列的时间复杂度为 $O(n^2)$
总的时间复杂度为 $O(n \log{n} + n^2) = O(n^2)$

空间复杂度： $O(\log{n})$ ，排序所需空间

参考：代码随想录

# LeetCode 435. 无重叠区间

435. Non-overlapping Intervals

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回需要移除区间的最小数量，使剩余区间互不重叠。

示例 1：

输入：intervals = [[1,2],[2,3],[3,4],[1,3]]
输出：1
解释：移除 [1,3] 后，剩下的区间没有重叠

示例 2：

输入：intervals = [[1,2],[1,2],[1,2]]
输出：2
解释：你需要移除两个 [1,2] 来使剩下的区间没有重叠

示例 3：

输入：intervals = [[1,2],[2,3]]
输出：0
解释：你不需要移除任何区间，因为它们已经是无重叠的了

提示：

$1 \le$ intervals.length $\le 10^5$
intervals[i].length == 2
$-5 \times 10^4 \le$ starti $<$ endi $\le 5 \times 10^4$

# Method: 排序 + 贪心

算法思路：

可以按照右边界 $end_i$ 进行排序，然后从左往右遍历数组、记录非重叠区间的个数，最后用总区间数减去非重叠区间数，即为所需移除的区间数
其中，记录非重叠区间个数时，应尽量保留右边界较小的区间 intervals[i] ，从而避免重叠。这是因为，前一个区间的右边界越小，留给下一个区间的空间就越大，从而保留更多的区间（即，移除更少的区间）

如下图所示（已按右边界升序排列），每次都是取最左侧的右边界作为分割点，来选取非重叠区间。首先，以区间 1 的右边界为分割点（保留区间 1）时，区间 2 和 3 均与 1 重叠（故而移除区间 2 和 3），找到的第一个不重叠区间是区间 4（故而保留区间 4），接着以区间 4 的右边界作为新的分割点，以此往复。最终，保留的区间为 1、4、6，非重叠区间的个数是 3，需移除的区间数为 6 - 3 = 3

代码实现：

static bool cmp(const vector<int>& a, const vector<int>& b) {
    return a[1] < b[1];
}

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), cmp); // 按右边界升序排列
    int count = 1;                         // 非重叠区间的个数
    int position = intervals[0][1];        // 分割点（非重叠区间的右边界）
    for (int i = 1; i < intervals.size(); i++) {
        if (intervals[i][0] >= position) { // 遇到非重叠区间
            count++;
            position = intervals[i][1];    // 更新分割点
        }
    }
    int ans = intervals.size() - count;    // 需移除的区间个数
    return ans;
}

时间复杂度： $O(n \log{n})$ ，其中 $n$ 是数组的长度

排序的时间复杂度为 $O(n \log{n})$
遍历数组的时间复杂度为 $O(n)$
总的时间复杂度为 $O(n \log{n} + n) = O(n \log{n})$

空间复杂度： $O(\log{n})$ ，排序所需空间（平均情况下）

参考：代码随想录

# LeetCode 45. 跳跃游戏 II

45. Jump Game II

给定一个长度为 n 的整数数组 nums ，初始位置为 nums[0] 。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处：

0 <= j <= nums[i]
i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1] 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：2
解释：跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2：

输入：nums = [2,3,0,1,4]
输出：2

提示：

$1 \le$ nums.length $\le 10^4$
$0 \le$ nums[i] $\le 1000$
题目保证可以到达 nums[n-1]

# 思路

贪心策略：

局部最优：尽可能往更远处跳跃
整体最远：每一步跳跃的距离尽可能大，从而减少跳跃次数

在具体实现上，我们不需要考虑每一步具体跳到哪里，只需关注每一步最远能跳到哪里即可

从左到右遍历数组，如果数组下标 i 到达当前这一步的最大覆盖位置、但还没有到达终点，即需要再跳跃一次（更新跳跃次数，并更新最大覆盖位置），直到终点在最大覆盖位置以内

# Method: 贪心

算法思路：

定义跳跃的步数 ans
定义两个覆盖范围：当前这一步的最大覆盖位置 curMaxPosition 和下一步最大覆盖位置 nextMaxPosition
遍历数组下标 i ，其中， i 最多移动到 nums.size() - 2 位置
- 更新下一步最大覆盖位置 nextMaxPosition
- 若下标 i 等于当前最大覆盖位置，说明从当前位置无法一步到达终点，至少需要多走一步
  - 更新跳跃的步数： ans++
  - 更新当前这一步的最大覆盖位置： curMaxPosition = nextMaxPosition;

其中， i 最大只能取 nums.size() - 2 ，是为了简化代码。特别地，当 i == nums.size() - 2 时，有以下两种情况

若 i 等于当前最大覆盖位置（即， curMaxPosition == nums.size() - 2 ），说明当前这一步无法到达终点，还需要再走一步才能到达终点（执行 ans++ ，遍历结束）
若 i 不等于当前最大覆盖位置（即， curMaxPosition > nums.size() - 2 ），说明当前这一步可以直接到达终点，无需再跳下一步（遍历结束，无需执行 ans++ ）

这两种情况可直接通过上述算法思路进行处理，无需再做额外的判定

代码实现：

int jump(vector<int>& nums) {
    int ans = 0;             // 步数
    int curMaxPosition = 0;  // 当前这一步可达的最远位置
    int nextMaxPosition = 0; // 下一步可到达的最远位置
    for (int i = 0; i < nums.size() - 1; i++) { // 注意这里是小于 nums.size() - 1
        nextMaxPosition = max(nextMaxPosition, i + nums[i]); // 更新 nextMaxPosition
        if (i == curMaxPosition) { // 到达当前这一步所能到达的最远位置 
            ans++;
            curMaxPosition = nextMaxPosition;
        }
    }
    return ans;
}

时间复杂度： $O(n)$ ，其中 $n$ 是数组长度

空间复杂度： $O(1)$

参考：

代码随想录
力扣官方题解

# LeetCode 452. 用最少数量的箭引爆气球

452. Minimum Number of Arrows to Burst Balloons

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中 points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend 之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart ， xend ，且满足 xstart ≤ x ≤ xend ，则该气球会被引爆。可以射出的弓箭的数量 没有限制 。弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用 2 支箭来爆破:
    在 x = 6 处射出箭，击破气球 [2,8] 和 [1,6] 。
    在 x = 11 处发射箭，击破气球 [10,16] 和 [7,12] 。

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要 4 支箭。

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用 2 支箭来爆破:
    在 x = 2 处发射箭，击破气球 [1,2] 和 [2,3] 。
    在 x = 4 处射出箭，击破气球 [3,4] 和 [4,5] 。

提示：

$1 \le$ points.length $\le 10^5$
points[i].length == 2
$-2^{31} \le$ xstart $<$ xend $\le 2^{31} - 1$

# 思路

每支箭应尽量多引爆气球，以使得所需箭的数量最小（贪心策略）

由图可知，应选择「最左侧的右边界」作为箭的发射点（如上图中的 1-3 所示），以尽可能多地引爆气球

也可以选择「最右侧的左边界」作为箭的发射点

# Method: 排序 + 贪心

算法思路：

先对数组 points 排序：按照第二个维度（气球的右边界位置）从小到大进行排序
遍历数组 points ，确定箭的发射点，并计算箭的数量
- 最初时， points[0] 的右边界（即， points[0][1] ）就是第一支箭的发射点，并且，气球左边界在发射点左侧（即，满足 points[i][0] <= points[0][1] 条件）的所有气球 i 均会被这一箭引爆（因为发射点在气球 i 的左右边界以内）
- 若出现 points[j][0] > points[0][1] ，即，气球 j 的左边界在发射点右侧，气球 j 不会被引爆，故而需要下一支箭。下一支箭的发射点就是 points[j][1] ，因为 points[j][1] 就是剩余气球中的右边界最小值，即，「最左侧的右边界」
- 依此类推

代码实现：

static bool cmp(const vector<int>& a, const vector<int> & b) {
    return a[1] < b[1];
}

int findMinArrowShots(vector<vector<int>>& points) {
    sort(points.begin(), points.end(), cmp); // 按 xend 升序排列
    int ans = 1;   // 至少需要 1 支箭
    int position = points[0][1];    // 第一支箭的发射点
    for (const vector<int>& ballon : points) {
        if (ballon[0] > position) { // 无法引爆 ballon
            ans++; // 需要多加 1 支箭
            position = ballon[1];   // 下一支箭的发射点
        }
    }
    return ans;
}

时间复杂度： $O(n \log{n})$ ，其中 $n$ 是数组的长度

排序的时间复杂度为 $O(n \log{n})$
遍历数组的时间复杂度为 $O(n)$
总的时间复杂度为 $O(n \log{n})$

空间复杂度： $O(\log{n})$ ，排序所需空间（平均情况下）

参考：力扣官方题解

# LeetCode 455. 分发饼干

455. Assign Cookies

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i ，都有一个胃口值 g[i] ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 s[j] 。如果 s[j] >= g[i] ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1：

输入：g = [1,2,3], s = [1,1]
输出：1

示例 2：

输入：g = [1,2], s = [1,2,3]
输出：2

提示：

$1 \le$ g.length $\le 3 \times 10^4$
$0 \le$ s.length $\le 3 \times 10^4$
$1 \le$ g[i] , s[j] $\le 2^{31} - 1$

# 思路

为满足尽可能多的孩子，应尽可能将饼干全部分发出去

于是，大尺寸的饼干应该优先分配给胃口大的孩子，这样才能使发出去的饼干尽可能多

可以采用贪心策略，选择每一阶段的局部最优（大尺寸饼干分配给胃口大的），从而达到全局最优（分发出的饼干数量达到最大）

也可以换一个思路：先将小尺寸饼干分配给胃口小的孩子，可参考代码随想录：分发饼干

# Method: 排序 + 贪心

算法思想：

分别将饼干尺寸数组 s 和小孩胃口数组 g 排序
将数组 g 的索引记为 i ，初始化为 i = g.size() - 1 ，对应于胃口最大的孩子；将数组 s 的索引记为 j ，初始化为 j = s.size() - 1 ，对应于尺寸最大的饼干
遍历数组 s （从后往前遍历）：
- 如果 s[j] >= g[i] ，说明饼干 j 能满足孩子 i ，即，当前剩余的、尺寸最大的饼干能够满足孩子 i ，将其分给孩子 i 。执行 j-- 和 i-- （考虑是否将下一个饼干分给下一个孩子）
- 如果 s[j] < g[i] ，说明饼干 j 不能满足孩子 i 。执行 i-- （考虑是否将当前饼干分发给下一个孩子）

代码实现：

int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end()); // 排序
    sort(s.begin(), s.end());
    int ans = 0;
    for (int i = g.size() - 1, j = s.size() - 1; i >= 0 && j >= 0; i--) { // 从后往前遍历
        if (s[j] >= g[i]) { // 饼干 j 可以分配给孩子 i
            j--;
            ans++;
        }
    }
    return ans;
}

时间复杂度： $O(m \log{m} + n \log{n})$ ，其中 $m$ 和 $n$ 分别是数组 g 和数组 s 的长度

对两个数组进行排序的时间复杂度为 $O(m \log{m} + n \log{n})$
遍历两个数组的时间复杂度为 $O(m + n)$
因此，总的时间复杂度为 $O(m \log{m} + n \log{n} + m + n) = O(m \log{m} + n \log{n})$

空间复杂度： $O(\log{m} + \log{n})$ ，考虑了排序所需的额外空间（平均情况下）

参考：力扣官方题解

# LeetCode 53. 最大子数组和

53. Maximum Subarray

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

$1 \le$ nums.length $\le 10^5$
$-10^4 \le$ nums[i] $\le 10^4$

进阶：如果你已经实现复杂度为 $O(n)$ 的解法，尝试使用更为精妙的分治法求解。

# Method 1: 贪心

贪心策略：

局部最优：当「连续子数组和」为负数时，放弃当前的连续子数组，从下一位元素重新开始新的连续子数组，即，需从下一个元素重新计算「连续子数组和」。这是因为：负的「连续子数组和」与下一个元素之和必定小于下一个元素本身
全局最优：选取最大的「连续子数组和」

代码实现：

int maxSubArray(vector<int>& nums) {
    int count = 0;
    int result = INT_MIN;
    for (int i = 0; i < nums.size(); i++) {
        count += nums[i];            // 连续子数组和
        result = max(result, count); // 连续子数组和的最大值
        if (count < 0) count = 0;    // 子数组和为负数，重新开始子数组
    }
    return result;
}

须注意，因为 nums[i] 可能为负数， result 需初始化为 INT_MIN

时间复杂度： $O(n)$ ，其中 $n$ 是数组 nums 的长度

空间复杂度： $O(1)$

参考：代码随想录

# Method 2: 动态规划

算法思路：

定义 dp[i] 表示以 nums[i] 结尾的连续子数组的最大和

对于任意 nums[i] 而言，可以将 nums[i] 添加到当前的连续子数组，此时的最大和为 dp[i - 1] + nums[i] ，也可以重新开始一个连续子数组，此时的最大和为 nums[i] 。综合两种情况取最大值，即，递推公式为 dp[i] = max(dp[i - 1] + nums[i], nums[i])

初始化： dp[0] = nums[0]

按 i 从小到大顺序遍历即可

遍历结束后，从 dp 数组中找到最大值，即为最大的连续子数组的和

代码实现：

int maxSubArray(vector<int>& nums) {
    vector<int> dp(nums.size(), 0);
    dp[0] = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        dp[i] = max(dp[i - 1] + nums[i], nums[i]);
    }
    int ans = INT_MIN; // 最大连续子数组的和
    for (int i = 0; i < nums.size(); i++) {
        if (dp[i] > ans) ans = dp[i];
    }
    return ans;
}

时间复杂度： $O(n)$ ，其中 $n$ 是数组 nums 的长度

空间复杂度： $O(n)$

可以采用滚动数组的思想降低空间复杂度，即：

int maxSubArray(vector<int>& nums) {
    int dp = 0;
    int ans = INT_MIN;
    for (int i = 0; i < nums.size(); i++) {
        dp = max(dp + nums[i], nums[i]);
        ans = max(ans, dp);
    }
    return ans;
}

时间复杂度： $O(n)$ ，其中 $n$ 是数组 nums 的长度

空间复杂度： $O(1)$

# LeetCode 55. 跳跃游戏

55. Jump Game

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

$1 \le$ nums.length $\le 10^4$
$0 \le$ nums[i] $\le 10^5$

# Method: 贪心

如果能够从当前位置到达 index 位置，也就能够从当前位置到达 index 左侧任意位置

因此，我们可以遍历数组中的每一个位置，计算「从当前位置出发所能到达的最远位置」，简称为 可到达的最远位置

如果 可到达的最远位置 在数组尾端以右，则数组尾端在可到达范围内

# 写法一

算法思路：

遍历当前位置 i ，其中， i 只能在可到达的位置范围内移动
- 更新可到达的最远位置
- 如果可到达的最远位置在数组尾端以右，返回 true
如果遍历结束时，数组尾端仍不在可到达范围内，返回 false

代码实现：

bool canJump(vector<int>& nums) {
    int rightMost = 0;                     // 可到达的最远位置
    for (int i = 0; i <= rightMost; i++) { // i 只能在可到达范围内移动
        rightMost = max(i + nums[i], rightMost);       // 更新可到达的最远位置
        if (rightMost >= nums.size() - 1) return true; // 终点在可到达范围内
    }
    return false; // 终点不在可到达范围内
}

# 写法二

算法思路：

遍历当前位置 i ，其中， i 可以在数组范围中移动
- 如果位置 i 超出可到达范围，位置 i 不可达，返回 false
- 否则，更新可到达范围
如果遍历结束，说明数组尾端是可到达的，返回 true

代码实现：

bool canJump(vector<int>& nums) {
    int rightMost = 0; // 可到达的最远位置
    for (int i = 0; i < nums.size(); i++) {
        if (i > rightMost) return false;         // 位置 i 不可达
        rightMost = max(rightMost, i + nums[i]); // 更新可到达的最远位置
    }
    return true;
}

时间复杂度： $O(n)$ ，其中 $n$ 是数组 prices 的长度

空间复杂度： $O(1)$

参考：

力扣官方题解
Ikaruga：别想那么多，就挨着跳吧

# LeetCode 56. 合并区间

56. Merge Intervals

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals [i] = [ $\textrm{start}_i$ , $\textrm{end}_i$ ] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

$1 \le$ intervals.length $\le 10^4$
intervals[i].length == 2
$0 \le$ starti $\le$ endi $\le 10^4$

# Method: 排序 + 贪心

算法思路

按第一维度（区间的左边界）排序
合并区间：每遇到两个重叠区间时，取两区间中的最小的左边界作为新区间的左边界，取两区间中的最大的右边界作为新区间的右边界
- 由于 intervals 按区间左边界升序排列，前一个区间的左边界就是合并所得区间的左边界
- 注意，合并后的区间可能会跟后续区间重叠，此时，需要继续合并

为解决区间的连续合并问题，可以采用以下方案：

首先将第一个区间（即， intervals[0] ）加入到结果数组 result
考虑第二个区间，看其是否与结果数组中的区间（即，区间 result.back() ）重叠（即，判断 intervals[1][0] 是否小于 result.back()[1] ）
- 若重叠，修改结果数组中的区间的右边界，即，将 result.back()[1] 修改为 max(result.back()[1], intervals[1][1])
- 若不重叠，将第二个区间加入到结果数组，即， result.push_back(intervals[1])
继续考虑下一区间，看其是否与区间 result.back() 重叠，处理方式与上一步相同

代码实现：

static bool cmp(const vector<int>& a, const vector<int>& b) {
    return a[0] < b[0];
}

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), cmp); // 按第一维度升序排序
    vector<vector<int>> result;                    // 结果数组
    result.push_back(intervals[0]);                // 将第一个区间加入到结果数组
    for (int i = 1; i < intervals.size(); i++) {
        if (intervals[i][0] <= result.back()[1])   // 区间重叠，合并两区间
            result.back()[1] = max(result.back()[1], intervals[i][1]);
        else                                       // 区间不重叠，将其加入到结果数组
            result.push_back(intervals[i]);
    }
    return result;
}

时间复杂度： $O(n \log{n})$ ，其中 $n$ 是区间的个数

排序的时间复杂度为 $O(n \log{n})$ ，遍历 intervals 的时间复杂度为 $O(n)$

空间复杂度： $O(\log{n})$ ，排序所需空间

参考：代码随想录

# LeetCode 714. 买卖股票的最佳时机含手续费

714. Best Time to Buy and Sell Stock with Transaction Fee

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

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

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1：

输入：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

示例 2：

输入：prices = [1,3,7,5,10,3], fee = 3
输出：6

提示：

$1 \le$ prices.length $\le 5 \times 10^4$
$1 \le$ prices[i] $< 5 \times 10^4$
$0 \le$ fee $< 5 \times 10^4$

# Method 1: 贪心

算法思路：

定义 buy 表示当前所持股票的最低成本（买入价与手续费之和），初始化为 prices[0] + fee 。定义 result 表示总利润，初始化为 0

遍历 prices 数组（以 i 为下标索引）：

情况一：如果当前股票价格 price[i] 与 fee 之和小于 buy ，说明我们能够以更低的成本买入当前股票，更新 buy 为 prices[i] + fee （相当于撤销之前的买入、以当前价格买入）
情况二：如果当前股票价格 prices[i] 大于 buy ，可以考虑卖出当前股票并收获 prices[i] - buy 的利润
- 之后的股票价格可能会持续上升，此时，应继续持有当前股票，以继续获取后续利润
- 之后的股票价格也可能先降后升，此时，应卖出当前股票，之后再重新买入
- 为综合处理以上两种情况，我们可以直接计算当前的利润，即 result += prices[i] - buy ，并将 buy 更新为 prices[i] 。如果之后的股票价格持续上升，则可以继续按 result += prices[i] - buy 更新利润（视为继续持有股票）；如果之后的股票价格先降后升，则可以在 prices[i] + fee < buy 条件下，将 buy 更新为 prices[i] + fee （视为当前股票已经卖出，并在股票下降过程中重新买入股票，对应于情况一）
情况三：股票价格 prices[i] 介于 buy - fee 与 buy 之间，不予操作（因为此时买入不便宜，卖出则会亏本）

代码实现：

int maxProfit(vector<int>& prices, int fee) {
    int result = 0;
    int buy = prices[0] + fee;
    for (int i = 1; i < prices.size(); i++) {
        if (prices[i] + fee < buy)     // 能够以更低的价格买入
            buy = prices[i] + fee;     // 更新 买入价与手续费之和
        else if (prices[i] > buy) {    // 当前价格 高于 买入价与手续费之和
            result += prices[i] - buy; // 计算利润
            buy = prices[i];           // 以当前价格重新买入股票（免手续费），因为可能出现更高价格
        }
    }
    return result;
}

时间复杂度： $O(n)$ ，其中 $n$ 是数组的长度

空间复杂度： $O(1)$

参考：力扣官方题解

# Method 2: 动态规划

算法思路：与 LeetCode 122. 买卖股票的最佳时机 II 基本相同，只需在买入股票（或者，卖出股票）时扣除手续费

这里考虑在卖出股票时扣除手续费

代码实现：

int maxProfit(vector<int>& prices, int fee) {
    int n = prices.size();
    vector<vector<int>> dp(n, vector<int>(2, 0));
    dp[0][0] = 0;           // 第 0 天不持有股票
    dp[0][1] = - prices[0]; // 第 0 天持有股票
    for (int i = 1; i < n; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee); // 第 i 天不持有股票
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);       // 第 i 天持有股票
    }
    return dp[n - 1][0];
}

时间复杂度： $O(n)$ ，其中 $n$ 是数组的长度

空间复杂度： $O(n)$

# LeetCode 738. 单调递增的数字

738. Monotone Increasing Digits

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回小于或等于 n 的最大数字，且数字呈 单调递增 。

示例 1：

输入：n = 10
输出：9

示例 2：

输入：n = 1234
输出：1234

示例 3：

输入：n = 332
输出：299

提示：

$0 \le$ n $\le 10^9$

# Method: 贪心

算法思路：

首先应将 n 转换为字符串类型的对象 strNum ，如果出现 strNum[i - 1] > strNum[i] 的情况，说明 strNum 并不是单调递增

此时，可将 strNum[i - 1] 自减 1 ，并考虑将 strNum[i] 置为 9 ，即确保第 i - 1 位和第 i 位组成最大的、单调递增的整数（贪心策略中的局部最优）

按上述操作处理 strNum[i - 1] 和 strNum[i] 时，还需做以下考虑：

将 strNum[i - 1] 减 1 后，可能导致 strNum[i - 2] > strNum[i - 1] ，即，需对 strNum[i - 2] 进行判断和处理。因此，应按照从右往左的顺序遍历 i
将 strNum[i] 置为 9 后，也应将第 i + 1 位、第 i + 2 位、 ... 、第 strNum.size() - 1 位也全都置为 9 ，以得到最大的、单调递增的整数。因此，需找到满足 strNum[i - 1] > strNum[i] 的最小的 i （不妨将其记作 start ），将 start 及其以后所有位上的数字均置为 9

代码实现：

int monotoneIncreasingDigits(int n) {
    string strNum = to_string(n);        // 将 n 转换为字符串
    int start = strNum.size();           // 赋数字 9 的起点
    for (int i = strNum.size() - 1; i > 0; i--) { // 从右往左遍历
        if (strNum[i - 1] > strNum[i]) { // 高位数大于低位数，高位数应减 1，并更新赋 9 的起点
            strNum[i - 1]--;
            start = i;
        }
    }
    for (int i = start; i < strNum.size(); i++) { // start 及其以后位置都需赋 9
        strNum[i] = '9';
    }
    int ans = stoi(strNum);
    return ans;
}

注意：需先找到 start ，然后再将 start 及其以后所有位上的数字均置为 9 。不能一边判断 if(strNum[i - 1] > strNum[i]) 条件是否成立、一边处理 strNum[i]

尤其是，不能将 strNum[i] = '9' 放在 if(strNum[i - 1] > strNum[i]) 的语句块内执行
因为其并不一定会将 start 及其以后的每一位均置为 9 ，以 n = 6352 为例，若将 strNum[i] = '9' 放在 if(strNum[i - 1] > strNum[i]) 的语句块内执行，得到的最终结果将会是 5949 ，而不是 5999

时间复杂度： $O(m)$ ，其中 $m$ 是数字 n 的长度

空间复杂度： $O(m)$ ，考虑了存储数字 n 的字符串

参考：代码随想录

# LeetCode 763. 划分字母区间

763. Partition Labels

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
    划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
    每个字母最多出现在一个片段中。
    像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

提示：

$1 \le$ s.length $\le 500$
s 仅由小写英文字母组成

# 思路

同一个字母只能出现在同一个片段，因此，需要遍历字符串，得到每个字母最后一次出现的位置

寻找每个片段可能的最小结束位置，以将字符串划分为尽可能多的片段（贪心策略）

# Method: 贪心

算法思路：

利用数组 hash 中的元素 hash[s[i] - 'a'] 来记录字母 s[i] 最后一次出现的位置
从左到右遍历字符串，在遍历的同时，维护当前片段的长度 count 以及当前片段的边界 boundary ，初始时 count = 0 、 boundary = 0
- 对于每个字母 s[i] ，其最后一次出现的位置一定在当前片段的边界以内，故而，应按照 boundary = max(boundary, hash[s[i] - 'a']) 更新片段的边界。此外，片段长度应加 1，即， count = count + 1
- 当遍历到边界 boundary （即， i == boundary ）时，片段涵盖的字母也仅出现在当前的 boundary 以左，即，当前片段结束。然后重置 count ，继续确定下一片段

代码实现：

vector<int> partitionLabels(string s) {
    vector<int> hash(26, 0);
    for (int i = 0; i < s.size(); i++) // 统计每一个字符最后出现的位置
        hash[s[i] - 'a'] = i;
    vector<int> result; // 目标数组
    int count = 0;      // 当前片段的长度
    int boundary = 0;   // 当前片段的边界
    for (int i = 0; i < s.size(); i++) {
        boundary = max(boundary, hash[s[i] - 'a']); // 更新边界
        count++;        // 更新片段长度
        if (i == boundary) {         // 当前片段结束
            result.push_back(count); // 将片段长度添加到目标数组
            count = 0;  // 重置，以统计下一个片段的长度
        }
    }
    return result;
}

时间复杂度： $O(n)$ ，其中 $n$ 是字符串的长度

空间复杂度： $O(1)$ ，本题使用的哈希数组是固定大小的（不考虑存储答案的数组）

参考：

力扣官方题解
代码随想录

# LeetCode 860. 柠檬水找零

860. Lemonade Change

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、 10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1：

输入：bills = [5,5,5,10,20]
输出：true
解释：
    前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
    第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
    第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
    由于所有客户都得到了正确的找零，所以我们输出 true。

示例 2：

输入：bills = [5,5,10,10,20]
输出：false
解释：
    前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
    对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
    对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
    由于不是每位顾客都得到了正确的找零，所以答案是 false。

提示：

$1 \le$ bills.length $\le 10^5$
bills[i] 不是 5 就是 10 或是 20

# Method: 模拟 + 贪心

算法思路：按顺序处理顾客的订单（模拟）

若顾客支付的是 5 美元，直接收银，无需找零
若顾客支付的是 10 美元，需找零 5 美元
若顾客支付的是 20 美元，有两种找零方式
- 方式一：找零一张 5 美元、一张 10 美元
- 方式二：找零三张 5 美元
- 应优先采用方式一找零，即，尽量保留 5 美元，以便之后遇到 10 美元、20 美元时也能找零（贪心）

代码实现：

bool lemonadeChange(vector<int>& bills) {
    int five = 0; // 现有的 5 美元数量
    int ten = 0;  // 现有的 10 美元数量
    for (auto i : bills) {
        if (i == 5) five++;  // 顾客支付 5 美元
        if (i == 10) {       // 顾客支付 10 美元
            if (five >= 1) { // 找零 5 美元
                ten++;
                five--;
            }
            else return false; // 无法找零
        }
        if (i == 20) {       // 顾客支付 20 美元
            if (five >= 1 && ten >= 1) { // 找零一张 5 美元、一张 10 美元
                five--;
                ten--;
            }
            else if (five >= 3) { // 找零三张 5 美元
                five -= 3;
            }
            else return false; // 无法找零
        }
    }
    return true; // 所有顾客均可找零
}

贪心

# LeetCode 1005. K 次取反后最大化的数组和

# 思路

# Method: 贪心

# LeetCode 122. 买卖股票的最佳时机 II

# 思路

# Method 1: 贪心

# Method 2: 动态规划

# LeetCode 134. 加油站

# 思路

# Method 1

# Method 2

# LeetCode 135. 分发糖果

# 思路

# Method: 贪心

# LeetCode 376. 摆动序列

# Method: 贪心

# LeetCode 406. 根据身高重建队列

# Method

# LeetCode 435. 无重叠区间

# Method: 排序 + 贪心

# LeetCode 45. 跳跃游戏 II

# 思路

# Method: 贪心

# LeetCode 452. 用最少数量的箭引爆气球

# 思路

# Method: 排序 + 贪心

# LeetCode 455. 分发饼干

# 思路

# Method: 排序 + 贪心

# LeetCode 53. 最大子数组和

# Method 1: 贪心

# Method 2: 动态规划

# LeetCode 55. 跳跃游戏

# Method: 贪心

# 写法一

# 写法二

# LeetCode 56. 合并区间

# Method: 排序 + 贪心

# LeetCode 714. 买卖股票的最佳时机含手续费

# Method 1: 贪心

# Method 2: 动态规划

# LeetCode 738. 单调递增的数字

# Method: 贪心

# LeetCode 763. 划分字母区间

# 思路

# Method: 贪心

# LeetCode 860. 柠檬水找零

# Method: 模拟 + 贪心

LeetCode - 回溯专题

LeetCode - 动态规划专题