首页Coding

# 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≤1 \le nums.length ≤104\le 10^4
  • −100≤-100 \le nums[i] ≤100\le 100
  • $1 \le $ k ≤104\le 10^4

# 思路

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

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

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

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

# Method: 贪心

贪心策略：

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

算法思路：

  1. 将数组 按照绝对值的大小从大到小排序

  2. 从左往右遍历 数组，在修改次数限制下，将遇到的每一个负数修改为相反数，并更新剩余修改次数（即，执行 k-- ）

  3. 如果剩余修改次数为奇数，将绝对值最小的数修改为相反数

  4. 计算数组和

代码实现：

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)O(n)，其中 nn 为数组长度


    

  • 排序的时间复杂度为 O(nlog⁡n)O(n \log{n})，这里不予考虑
    • 

  • 修改数组、计算数组和的时间复杂度均为 O(n)O(n)
    • 



空间复杂度：O(1)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≤1 \le  prices.length  ≤3×104\le 3 \times 10^4
    • 

  • 0≤0 \le  prices[i]  ≤104\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)O(n)，其中 nn 是数组  prices  的长度


空间复杂度：O(1)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)O(n)，其中 nn 是数组  prices  的长度


空间复杂度：O(n)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≤1 \le  n  ≤105\le 10^5
    • 

  • 0≤0 \le  gas[i] ,  cost[i]  ≤104\le 10^4
    • 



# 思路


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




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




即，如果存在一个可行的出发站点，则必然是 j+1j + 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)O(n)，其中 nn 是数组长度


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


参考：力扣官方题解


# Method 2


算法思路：


    

  1. 

    定义  totalSum  ，用于累计每个站点的剩余油量，以判断是否存在一个可行的出发站点
    

    2. 

  2. 

    定义  curSum  ，用于累计从某个站点出发至今的剩余油量（最初从站点  0  开始累计）
    

    3. 

  3. 

    定义  start  ，作为当前考虑的出发站点
    

    4. 

  4. 

    从左往右遍历站点  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  出发的剩余油量
          • 

        

        • 

      

      • 

    

    5. 

  5. 

    遍历结束，判断  totalSum  是否小于 0
    

      

    • 若小于 0 ，说明  gas  之和小于  cost  之和，不存在可行的出发站点，返回  -1
      • 

    • 若不小于 0 ，说明存在一个可行的出发站点，并且，该出发站点即为  start
      • 

    

    6. 



代码实现：


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)O(n)，其中 nn 是数组长度


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


参考：代码随想录


附：


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


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


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



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


∑i=0ans−1(gas[i]−cost[i])+∑i=ansgas.size()−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



即：


∑i=ansgas.size()−1(gas[i]−cost[i])>∑i=0ans−1(cost[i]−gas[i])\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≤1 \le  n  ≤2×104\le 2 \times 10^4
    • 

  • 0≤0 \le  ratings[i]  ≤2×104\le 2 \times 10^4
    • 



# 思路


考虑以下两个规则：


    

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

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



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




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




# Method: 贪心


算法思路：


    

  1. 

    定义数组  nums  记录每个孩子应得糖果的数量
    

    2. 

  2. 

    处理「左规则」：从左往右遍历（只能是从左往右遍历，因为右边孩子的糖果数需要根据左边孩子糖果数的变化而变化）：
    

      

    • 若  ratings[i] > ratings[i - 1]  ，则  i  应比  i - 1  多得一颗糖果，即  nums[i] = nums[i - 1] + 1
      • 

    

    3. 

  3. 

    处理「右规则」：从右往左遍历（只能是从右往左遍历，因为左边孩子的糖果数需要根据右边孩子糖果数的变化而变化）
    

      

    • 若  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)
        • 

      

      • 

    

    4. 

  4. 

    计算糖果总数：求数组  nums  的元素和
    

    5. 



代码实现：


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)O(n)，其中 nn 是数组  ratings  的长度


空间复杂度：O(n)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≤1 \le  nums.length  ≤1000\le 1000

0≤0 \le  nums[i]  ≤1000\le 1000


进阶：你能否用 O(n)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)O(n)，其中 nn 是数组的长度


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


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




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




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


406. Queue Reconstruction by Height


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


请你重新构造并返回输入数组  people  所表示的队列。返回的队列应该格式化为数组  queue  ，其中  queue[j]  = [hj, kj] 是队列中第 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≤1 \le  people.length  ≤2000\le 2000
    • 

  • 0≤hi≤1060 \le h_i \le 10^6
    • 

  • 0≤ki<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  插入到队列的位置 kik_i （优先处理 hih_i 值较大的  i ）




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




插入的过程：


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(n2)O(n^2)，其中 nn 是数组的长度


    

  • 排序的时间复杂度为 O(nlog⁡n)O(n \log{n})
    • 

  • 重建队列的时间复杂度为 O(n2)O(n^2)
    • 

  • 总的时间复杂度为 O(nlog⁡n+n2)=O(n2)O(n \log{n} + n^2) = O(n^2)
    • 



空间复杂度：O(log⁡n)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≤1 \le  intervals.length  ≤105\le 10^5
    • 

  • intervals[i].length == 2
    • 

  • −5×104≤-5 \times 10^4 \le  starti  <<  endi  ≤5×104\le 5 \times 10^4
    • 



# Method: 排序 + 贪心


算法思路：


    

  • 

    可以按照右边界 endiend_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(nlog⁡n)O(n \log{n})，其中 nn 是数组的长度


    

  • 排序的时间复杂度为 O(nlog⁡n)O(n \log{n})
    • 

  • 遍历数组的时间复杂度为 O(n)O(n)
    • 

  • 总的时间复杂度为 O(nlog⁡n+n)=O(nlog⁡n)O(n \log{n} + n) = O(n \log{n})
    • 



空间复杂度：O(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≤1 \le  nums.length  ≤104\le 10^4
    • 

  • 0≤0 \le  nums[i]  ≤1000\le 1000
    • 

  • 题目保证可以到达  nums[n-1]
    • 



# 思路


贪心策略：


    

  • 局部最优：尽可能往更远处跳跃
    • 

  • 整体最远：每一步跳跃的距离尽可能大，从而减少跳跃次数
    • 



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


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




# Method: 贪心


算法思路：


    

  1. 

    定义跳跃的步数  ans
    

    2. 

  2. 

    定义两个覆盖范围：当前这一步的最大覆盖位置  curMaxPosition   和 下一步最大覆盖位置  nextMaxPosition
    

    3. 

  3. 

    遍历数组下标  i  ，其中， i  最多移动到  nums.size() - 2  位置
    

      

    • 更新下一步最大覆盖位置  nextMaxPosition
      • 

    • 若下标  i  等于当前最大覆盖位置，说明从当前位置无法一步到达终点，至少需要多走一步

        

      • 更新跳跃的步数： ans++
        • 

      • 更新当前这一步的最大覆盖位置： curMaxPosition = nextMaxPosition;
        • 

      

      • 

    

    4. 



其中， 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)O(n)，其中 nn 是数组长度


空间复杂度：O(1)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≤1 \le  points.length  ≤105\le 10^5
    • 

  • points[i].length == 2
    • 

  • −231≤-2^{31} \le  xstart  <<  xend  ≤231−1\le 2^{31} - 1
    • 



# 思路


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




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




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




# Method: 排序 + 贪心


算法思路：


    

  1. 

    先对数组  points  排序：按照第二个维度（气球的右边界位置）从小到大进行排序
    

    2. 

  2. 

    遍历数组  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]  就是剩余气球中的右边界最小值，即，「最左侧的右边界」
      

      • 

    • 

      依此类推
      

      • 

    

    3. 



代码实现：


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(nlog⁡n)O(n \log{n})，其中 nn 是数组的长度


    

  • 排序的时间复杂度为 O(nlog⁡n)O(n \log{n})
    • 

  • 遍历数组的时间复杂度为 O(n)O(n)
    • 

  • 总的时间复杂度为 O(nlog⁡n)O(n \log{n})
    • 



空间复杂度：O(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≤1 \le  g.length  ≤3×104\le 3 \times 10^4
    • 

  • 0≤0 \le  s.length  ≤3×104\le 3 \times 10^4
    • 

  • 1≤1 \le  g[i] ,  s[j]  ≤231−1\le 2^{31} - 1
    • 



# 思路


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


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


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




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




# Method: 排序 + 贪心


算法思想：


    

  1. 

    分别将饼干尺寸数组  s  和小孩胃口数组  g  排序
    

    2. 

  2. 

    将数组  g  的索引记为  i  ，初始化为  i = g.size() - 1  ，对应于胃口最大的孩子；将数组  s  的索引记为  j  ，初始化为  j = s.size() - 1  ，对应于尺寸最大的饼干
    

    3. 

  3. 

    遍历数组  s  （从后往前遍历）：
    

      

    • 如果  s[j] >= g[i]  ，说明饼干  j  能满足孩子  i  ，即，当前剩余的、尺寸最大的饼干能够满足孩子  i  ，将其分给孩子  i  。执行  j--  和  i--  （考虑是否将下一个饼干分给下一个孩子）
      • 

    • 如果  s[j] < g[i]  ，说明饼干  j  不能满足孩子  i  。执行  i--  （考虑是否将当前饼干分发给下一个孩子）
      • 

    

    4. 



代码实现：


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(mlog⁡m+nlog⁡n)O(m \log{m} + n \log{n})，其中 mm 和 nn 分别是数组  g  和数组  s  的长度


    

  • 对两个数组进行排序的时间复杂度为 O(mlog⁡m+nlog⁡n)O(m \log{m} + n \log{n})
    • 

  • 遍历两个数组的时间复杂度为 O(m+n)O(m + n)
    • 

  • 因此，总的时间复杂度为 O(mlog⁡m+nlog⁡n+m+n)=O(mlog⁡m+nlog⁡n)O(m \log{m} + n \log{n} + m + n) = O(m \log{m} + n \log{n})
    • 



空间复杂度：O(log⁡m+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≤1 \le  nums.length  ≤105\le 10^5
    • 

  • −104≤-10^4 \le  nums[i]  ≤104\le 10^4
    • 



进阶：如果你已经实现复杂度为 O(n)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)O(n)，其中 nn 是数组  nums  的长度


空间复杂度：O(1)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)O(n)，其中 nn 是数组  nums  的长度


空间复杂度：O(n)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)O(n)，其中 nn 是数组  nums  的长度


空间复杂度：O(1)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≤1 \le  nums.length  ≤104\le 10^4
    • 

  • 0≤0 \le  nums[i]  ≤105\le 10^5
    • 



# Method: 贪心


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


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


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


# 写法一


算法思路：


    

  1. 

    遍历当前位置  i  ，其中， i  只能在可到达的位置范围内移动
    

      

    • 更新可到达的最远位置
      • 

    • 如果可到达的最远位置在数组尾端以右，返回  true
      • 

    

    2. 

  2. 

    如果遍历结束时，数组尾端仍不在可到达范围内，返回  false
    

    3. 



代码实现：


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; // 终点不在可到达范围内
}
# 写法二


算法思路：


    

  1. 

    遍历当前位置  i  ，其中， i  可以在数组范围中移动
    

      

    • 如果位置  i  超出可到达范围，位置  i  不可达，返回  false
      • 

    • 否则，更新可到达范围
      • 

    

    2. 

  2. 

    如果遍历结束，说明数组尾端是可到达的，返回  true
    

    3. 



代码实现：


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)O(n)，其中 nn 是数组  prices  的长度


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


参考：



# LeetCode 56. 合并区间


56. Merge Intervals


以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals [i] = [starti\textrm{start}_i, endi\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≤1 \le  intervals.length  ≤104\le 10^4
    • 

  • intervals[i].length == 2
    • 

  • 0≤0 \le  starti  ≤\le  endi  ≤104\le 10^4
    • 



# Method: 排序 + 贪心


算法思路


    

  1. 

    按第一维度（区间的左边界）排序
    

    2. 

  2. 

    合并区间：每遇到两个重叠区间时，取两区间中的最小的左边界作为新区间的左边界，取两区间中的最大的右边界作为新区间的右边界
    

      

    • 由于  intervals  按区间左边界升序排列，前一个区间的左边界就是合并所得区间的左边界
      • 

    • 注意，合并后的区间可能会跟后续区间重叠，此时，需要继续合并
      • 

    

    3. 



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


    

  • 首先将第一个区间（即， 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(nlog⁡n)O(n \log{n})，其中 nn 是区间的个数


    

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



空间复杂度：O(log⁡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≤1 \le  prices.length  ≤5×104\le 5 \times 10^4
    • 

  • 1≤1 \le  prices[i]  <5×104< 5 \times 10^4
    • 

  • 0≤0 \le  fee  <5×104< 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)O(n)，其中 nn 是数组的长度


空间复杂度：O(1)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)O(n)，其中 nn 是数组的长度


空间复杂度：O(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≤0 \le  n  ≤109\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)O(m)，其中 mm 是数字  n  的长度


空间复杂度：O(m)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≤1 \le  s.length  ≤500\le 500
    • 

  • s  仅由小写英文字母组成
    • 



# 思路


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


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


# Method: 贪心


算法思路：


    

  1. 

    利用数组  hash  中的元素  hash[s[i] - 'a']  来记录字母  s[i]  最后一次出现的位置
    

    2. 

  2. 

    从左到右遍历字符串，在遍历的同时，维护当前片段的长度  count  以及当前片段的边界  boundary  ，初始时  count = 0  、 boundary = 0
    

      

    • 对于每个字母  s[i]  ，其最后一次出现的位置一定在当前片段的边界以内，故而，应按照  boundary = max(boundary, hash[s[i] - 'a'])  更新片段的边界。此外，片段长度应加 1，即， count = count + 1
      • 

    • 当遍历到边界  boundary （即， i == boundary  ）时，片段涵盖的字母也仅出现在当前的  boundary  以左，即，当前片段结束。然后重置  count  ，继续确定下一片段
      • 

    

    3. 





代码实现：


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)O(n)，其中 nn 是字符串的长度


空间复杂度：O(1)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≤1 \le  bills.length  ≤105\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; // 所有顾客均可找零
}