LeetCode 12 - 贪心

标签：12 return nums int ++ 数组 LeetCode dp 贪心

455. 分发饼干

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

方法：贪心

从贪心的角度考虑，应该按照孩子的胃口从小到大的顺序依次满足每个孩子，且对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干。

首先对数组 \(g\) 和 \(s\) 排序，然后从小到大遍历 \(*g*\) 中的每个元素，对于每个元素找到能满足该元素的 \(s\)中的最小的元素。

public int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);
    int i = 0, j = 0;
    while (i < g.length && j < s.length) {
        if (g[i] <= s[j]) i++;
        j++;
    }
    return i;
}

55. 跳跃游戏

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

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

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

方法：贪心

对于数组中任意一个位置 y，如何判断它是否可以到达？只要存在一个位置 x，它本身可以到达，并且它能够到达的最远位置能够到达 y，即 x+nums[x] >= y，那么位置 y 就能到达。

这样一来，依次遍历数组中每一个位置，实时维护 最远可以到达的位置 rightmost。那么，对于当前遍历到的位置 x，如果 x <= rightmost，那么就可以到达该位置，然后用 max(rightmost, x+nums[x]) 来更新 rightmost。

在遍历过程中，如果 rightmost 大于等于 nums.length，则说明能够到达最后一个位置。

 boolean canReach(int[] nums) {
     int n = nums.length;
     int rightmost = 0;
     for(int i = 0; i < n; i++) {
         // 如果当前位置可以到达
         if(i <= rightmost) {
             // 更新最远可以到达位置
             rightmost = Math.max(rightmost, i + nums[i]);
             if(rightmost >= n - 1)
                 return true;
         }
     }
     return false;
 }

45. 跳跃游戏 II

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置（假设你总是可以到达数组的最后一个位置），求出最少跳跃次数。

方法：贪心

贪心地正向查找，每次找到可到达的最远位置，就可以在限行时间内找到最少跳跃次数。

以数组 [2,3,1,2,4,2,3] 为例，从下标 0 出发，最远可以到达下标 2 ：

• 在这些可以到达的下标中，下标 1 可以进一步到达最远的位置，所以第一步先到达下标 1 ，将它记为 边界。
• 然后继续遍历，不断记录当前能够到达的最远位置，到达边界位置时，更新下一个边界的位置，同时将跳跃步数加一。
• 当最远到达位置到达最后一个位置后，就可以返回跳跃步数了。

在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。

public int jump(int[] nums) {
    int end = 0; // 边界
    int farmost = 0; // 最远可以到达的位置
    int steps = 0; // 跳跃步数
    for (int i = 0; i < nums.length - 1; i++) {
        farmost = Math.max(farmost, i + nums[i]);
        if (i == end) { // 到达前一个边界位置，更新下一个边界
            end = farmost;
            steps++;
        }
    }
    return steps;
}

376. 摆动序列

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

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

方法一：动态规划

一些约定概念：

• 上升 / 下降摆动序列：最后一个元素呈上升 / 下降态势的摆动序列。
• 波峰 / 波谷元素：处于序列中间，且大于左右两个邻居的元素，叫做波峰元素，如果处于序列两端，且大于旁边相邻元素，也叫作波峰元素。波谷元素同理。

1️⃣ dp 数组定义：

将一个元素添加到摆动序列末尾时，需要考虑上升 / 下降两种摆动序列，因此定义两个 dp 数组：

• up[i] ：前 i 个元素中以某个元素结尾的上升摆动序列的最大长度；
• down[i] ：前 i 个元素中以某个元素结尾的下降摆动序列的最大长度。

2️⃣ base case：

因为单个数字也属于摆动序列，所以 up[0] = down[0] = 1 。

3️⃣ 状态转移：

首先看 up 数组：

• 如果 nums[i] <= nums[i-1] ，则 up[i] = up[i-1] ；（因为所有以 nums[i] 结尾的上升摆动序列都可以用 nums[i-1] 结尾来代替，且长度不变。）
• 如果 nums[i] > nums[i-1]，则：
  • up[i] 可以从 up[i-1] 转移过来 —— up[i] = up[i-1] ；
  • 也可以从 down[i-1] 转移过来 —— up[i] = down[i-1] + 1 。

\[up[i]= \begin{cases} up[i-1], & nums[i] \leq nums[i-1] \\ \max (up[i-1],\; down[i-1]+1), & nums[i] > \text { nums }[i-1] \end{cases} \]

同理，可以得到 down 的状态转移方程：

\[down[i] = \begin{cases} down[i-1], & nums[i] \ge nums[i-1] \\ max(down[i-1], \; up[i-1]+1), & nums[i] < nums[i-1] \end{cases} \]

最终结果就是 up[n-1] 和 down[n-1] 的最大者。

public int wiggleMaxLength(int[] nums) {
        int len = nums.length;
    if (len < 2) return len;
    int[] up = new int[len];
    int[] down = new int[len];
    up[0] = down[0] = 1;
    for (int i = 1; i < len; i++) {
        if (nums[i] > nums[i-1]) {
            up[i] = Math.max(up[i-1], down[i-1] +1);
            down[i] = down[i-1];
        } else if (nums[i] < nums[i-1]) {
            up[i] = up[i-1];
            down[i] = Math.max(down[i-1], up[i-1] + 1);
        } else if (nums[i] == nums[i-1]) { // 相等，序列不变
            up[i] = up[i-1];
            down[i] = down[i-1];
        }
    }
    return Math.max(up[len-1], down[len-1]);
}

方法二：贪心

最长摆动序列包含了数组中所有的波峰和波谷，所以遍历数组，统计波峰波谷的数量即可，需要注意其中相邻的相同元素的情况。

在代码中，用 prevDiff 记录前面两个元素的差值，如果大于零表示前面是上坡，小于零表示前面是下坡。

public int wiggleMaxLength(int[] nums) {
    int n = nums.length;
    if (n < 2) return n;
    int prevDiff = nums[1] - nums[0];
    int result = prevDiff == 0 ? 1 : 2;
    for (int i = 2; i < n; i++) {
        int curDiff = nums[i] - nums[i-1];
        // 趋势为：∪ 形 或者 ∩ 形
        if ( (curDiff > 0 && prevDiff <= 0) 
                || (curDiff < 0 && prevDiff >= 0) ) {
            result++;
            prevDiff = curDiff;
        }
    }
    return result;
}

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组，返回其最大和。

方法一：动态规划

三步走：

• dp 数组：dp[i] 表示以 nums[i] 结尾的最大子数组和。
• base case：dp[0] = nums[0]。
• 状态转移：dp[i] = max(dp[i-1] + nums[i], nums[i]) （考虑前面的，或者不考虑前面的）

最后的结果就是整个 dp 数组中的那个最大值。

方法二：贪心

遍历数组，不断记录连续和 sum ，当 sum < 0 时立刻放弃当前记录的这个子数组，重新从下一个数开始计算连续和，因为负数只会 “拖累” 后面的子数组。同时，在遍历过程中不断更新最大连续和 maxSum ，最后返回这个值即可。

public int maxSubArray(int[] nums) {
    int n = nums.length;
    int maxSum = Integer.MIN_VALUE;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += nums[i];
        if (sum > maxSum) maxSum = sum;
        if (sum <= 0) sum = 0; // 放弃前面的序列
    }
    return maxSum;
}

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

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

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

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

方法：贪心

因为需要修改后的数组之和尽可能大，所以应该尽可能从小到大修改负数的符号，这样的贪心操作是最优的。（将负数 -x 修改成 x 会使得数组之和增加 2x）

如果 K 值大于负数的个数，那么就还得修改一些非负数：

• 如果存在 0 ，则剩余修改次数全用在这个 0 上，相当于没修改。
• 不存在 0 且剩余修改次数是偶数，那么也相当于没修改。
• 不存在 0 且剩余修改次数是奇数，选择最小那个正数修改一次即可。

需要注意，在修改负数的过程中，可能出现了更小的正数。

public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
      // 修改负数
      for (int i = 0; i < nums.length; i++) {
          if (k == 0) break;
          if (nums[i] < 0) {
              nums[i] = -nums[i];
              k--;
          }
      }
      int sum = 0;
      for (int num : nums) sum += num;
      // 修改最小的正数
      if (k > 0 && k % 2 == 1) {
          Arrays.sort(nums);
          sum -= 2 * nums[0];
      }
      return sum;
}

Stream 求和：Arrays.stream(nums).sum() 。

本题中数组元素的范围为 \([−100,100]\)，因此我们可以使用计数数组（桶）或者哈希表，直接统计每个元素出现的次数，再升序遍历元素的范围，这样就省去了排序需要的时间。

public int largestSumAfterKNegations(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
    freq.put(num, freq.getOrDefault(num, 0) + 1);
  }
    int sum = Arrays.stream(nums).sum();
    // 修改负数
    for (int i = -100; i < 0; ++i) {
        if (freq.containsKey(i)) {
            int count = Math.min(k, freq.get(i));
            sum -= 2 * i * count; // 对 count 个 i 进行修改
            // 更新 freq 字典
            freq.put(i, freq.get(i) - count);
            freq.put(-i, count + freq.getOrDefault(-i, 0));
            k -= count;
            if (k == 0) break;
        }
    }
    // 修改正数
    if (k > 0 && k % 2 == 1 && !freq.containsKey(0)) {
        // 遇见的第一个存在于 freq 中的正数，就是最小那个正数
        for (int i = 0; i <= 100; i++) {
            if (freq.containsKey(i)) {
                sum -= 2 * i;
                break;
            }
        }
    }
    return sum;
}

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

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

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

方法一：贪心

在某天 x 买入，在将来的某一天 x+i 卖出，所获利润是可以分解的，假如在第 0 天买入，在第 2 天卖出，那么利润为：

\[prices[2]-prices[0] = (prices[2]-prices[1])+(prices[1]-prices[0]) \]

这道题 「贪心」 的地方在于，对于 「今天的股价 - 昨天的股价」，得到的结果有 3 种可能：① 正数，② 0，③ 负数。贪心算法的决策是： 只加正数 。

public int maxProfit(int[] prices) {
    int n = prices.length;
    if (n < 2) return 0;
    int profit = 0;
    for (int i = 1; i < n; i++) {
        int diff = prices[i] - prices[i-1];
        if (diff > 0) profit += diff;
    }
    return profit;
}

方法二：动态规划

• dp 数组定义：dp[i][0] 表示第 i 天结束时不持有股票的最大收益，dp[i][1] 表示第 i 天结束时持有股票的最大收益。
• Base Case：dp[0][0] = 0 ，dp[0][1] = -prices[0] 。
• 状态转移：
  • dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])，昨天结束时本就不持有，或者昨天结束时持有，但今天卖出了。
  • dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])，昨天结束时本就持有，或者昨天结束时未持有，但今天买入了。
• 最终结果：dp[n-1][0]

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

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

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

返回获得利润的最大值。

方法一：动态规划

• dp 数组定义：dp[i][0] / dp[i][1] 分别表示第 i 天结束时手上不持有 / 持有股票的情况下，最大收益。
• Base Case：dp[0][0] = 0, dp[0][1] = -prices[0] 。
• 状态转移：
  • dp[i][0] ：可以从两种情况转移而来 —— 前一天结束时就没有股票，今天没有操作；前一天结束时持有股票，今天卖出（手续费）。 dp[i][0] = ax(dp[i-1][0], dp[i-1][1] + prices[i] - fee) 。
  • dp[i][1] ：同样可以从两种情况转移而来 —— 前一天结束时持有股票，今天没有操作；前一天结束时没有股票，今天买入（没有手续费）。dp[i][1] = dp[i-1][1], dp[i-1][0] - prices[i] 。
• 最终答案：max(dp[n-1][0], dp[n-1][1])

134. 加油站

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

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

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

方法：贪心

从第 i 个加油站开始，累计经过各个加油站之后油箱中所剩油的容量，一旦碰到累计容量小于 0 的加油站 j，则说明从 i 到 j 这几个加油站都不能作为起点。因为从这之间的任何一个加油站出发，到达 j 后所剩油的容量都会是负数。那么这时就要从 j+1 出发，重新尝试。

两点解释：

• 问题 1：为什么应该将起始站点设为k+1？
  • 因为 k->k+1 站耗油太大，0->k 站剩余油量都是不为负的，每减少一站，就少了一些剩余油量。所以如果从 k 前面的站点作为起始站，剩余油量不可能冲过 k+1 站。
• 问题 2：为什么如果 k+1->end 全部可以正常通行，且 rest>=0 就可以说明车子从 k+1 站点出发可以开完全程？（只需要从 k + 1 检查到数组末尾，不需要再检查 0 - k 是否满足，因为这已经隐式地满足了。）
  • 因为，起始点将当前路径分为 A、B 两部分。其中，必然有 (1) A部分剩余油量 < 0。(2) B部分剩余油量 > 0。
  • 所以，无论多少个站，都可以抽象为两个站点 A、B —— 从B站加满油出发，开往A站，车加油，再开回 B 站。
  • 如果存在答案，则必然有：B剩余的油 >= A缺少的油。

public int canCompleteCircuit(int[] gas, int[] cost) {
    int n = gas.length;
    int rest = 0;
    int start = 0;
    int sumOfRest = 0;
    for (int i = 0; i < n; i++) {
        rest += gas[i] - cost[i];
        sumOfRest += gas[i] - cost[i];
        if (rest < 0) {
            start = (i + 1) % n;
            rest = 0;
        }
    }
    if (sumOfRest >= 0) return start;
    return -1;
}

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求，给这些孩子分发糖果：

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

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

方法：贪心

「相邻的孩子中，评分高的孩子必须获得更多的糖果」这一条件可以分解为两部分：

• （左规则）如果 ratings[i-1] < ratings[i]，则第 i 个孩子分到的糖果比第 i-1 个孩子多一个；
• （右规则）如果 ratings[i-1] > ratings[i] ，则第 i-1 个孩子分到的糖果比第 i 个孩子多一个。

那么，分成两步来做：

• 首先从左往右遍历，使得糖果分配满足第一个条件（使递增序列正确分配），为每个孩子发left[i] 个糖。
• 然后从右往左遍历，使得糖果分配满足第二个条件（使递减序列正确分配），同时为每个孩子分配的糖果数量为 max(left[i], right) 个。

图片来源：https://leetcode.cn/problems/candy/solution/candy-cong-zuo-zhi-you-cong-you-zhi-zuo-qu-zui-da-/

public int candy(int[] ratings) {
    int n = ratings.length;
    if (n < 2) return 1;
    int candyNum = 0;
    int[] left = new int[n];
    int[] right = new int[n];
    Arrays.fill(left, 1);
    Arrays.fill(right, 1);
        // 从左往右遍历
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i-1]) {
            left[i] = 1 + left[i-1];
        }
    }
    candyNum += left[n-1];
        // 从右往左遍历
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i+1]) {
            right[i] = right[i+1] + 1;
        }
        candyNum += Math.max(left[i], right[i]);
    }
    return candyNum;
}

406. 根据身高重建队列

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

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人在这个队伍中的 真实属性，即第 j 个人前面真的刚好有 kj 个身高大于等于他的人。

一般这种数对，还涉及排序的，根据第一个元素正向排序，根据第二个元素反向排序，或者根据第一个元素反向排序，根据第二个元素正向排序，往往能够简化解题过程。

先按照身高从高到低的顺序对数对排序，这样一来，处理顺序就是先安排身高较高者的位置，然后安排较低者的位置，那么后面人的位置就不会影响前面已经安排好位置的人了。（k 记录的是身高 ≥ 自身的人的数量，所以比自己低的人不管在在自己前面还是后面都没关系）

还存在身高相同的情况，此时应该根据 k 从小到大排序，这样在几个身高相同的人之间，就会先给 k 值较小的人安排位置。因为 k 值较小的人最终肯定是排在较大的人前面的，给 k 值较小者安排位置时，不会考虑 k 值较大者的位置，但是给较大者安排位置时，需要考虑较小者的位置（较大者的 k 是包含了较小者的）。

public int[][] reconstructQueue(int[][] people) {
    // 按身高从高到低、k 从小到大排序
    Arrays.sort(people, new Comparator<int[]>() {
        public int compare(int[] p1, int[] p2) {
            if (p1[0] != p2[0]) return p2[0] - p1[0];
            else return p1[1] - p2[1];
        }
    });
        // 因为需要多次插入操作，所以使用链表
    LinkedList<int[]> list = new LinkedList<>();
    for (int[] p : people) {
        list.add(p[1], p);
    }
    return list.toArray(new int[list.size()][]);
}

435. 无重叠区间

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

方法一：动态规划

题目要求等价于 选出最多数量的区间，且它们互不重叠。

先将所有区间按照左端点（或者右端点）从小到大排序，设排完序后左端点分别为 \(l_0,l_1,...,l_{n-1}\)，右端点分别为 \(r_0,r_1,...,r_{n-1}\)，那么用 \(f_i\) 表示 以区间 i 作为最后一个区间，可以选出的区间数量的最大值，状态转移为：

\[f_i=\max(f_j) + 1, \quad j<i \text{ and }r_j\le l_i \]

即在所有位于区间 \(i\) 之前且与之不相交的区间 \(j\) 中，选择 \(f_j\) 最大的那个区间进行状态转移。如果这样的 \(j\) 不存在，那么上述状态转移方程的 \(\max\) 这一项就为 0，那么 \(f_i\) 就为 1。

最终答案即为 所有 \(f_i\) 中的最大值。

 int eraseOverlapIntervals(int[][] intervals) {
     Arrays.sort(intervals, new Comparator<int[]>() {
         public int compare(int[] interval1, int[] interval2) {
             // 按区间左端点从小到大排序
             return interval1[0] - interval2[0];
         }
     });
     int n = intervals.length;
     int[] f = new int[n];
     Arrays.fill(f, 1);
     for(int i = 1; i < n; i++) {
         for(int j = 0; j < i; j++) {
             if(intervals[j][1] <= intervals[i][0])
                 f[i] = Math.max(f[i], f[j]+1);
         }
     }
     return n - Arrays.stream(f).max().getAsInt();
 }

方法二：贪心

应该选择哪个区间作为首个区间呢？就是 右端点最小的那个区间。(右端点越小，给后面的区间留出的空间越大) 因此将所有区间 按照右端点从小到大进行排序，之后第一个区间就是我们要选择的首个区间。

确定了首个区间之后，所有与首个区间不重合的区间就组成了一个规模更小的子问题，接着只要找出其中右端点最小的区间即可。用相同的方法，可以确定后续所有区间。

在代码编写中，我们对按照右端点排好序的区间进行遍历，并实时维护一个已选择区间的右端点 right，如果当前区间与上一个已选择区间不重合，即当前区间的左端点大于等于 right，则贪心地选择这个区间，并将 right 更新为这个区间的右端点。

 int eraseOverlapIntervals(int[][] intervals) {
     Arrays.sort(intervals, new Comparator<int[]>() {
         public int compare(int[] a, int[] b) {
             return a[1] - b[1]; // 按右端点从小到大排序
         }
     });
     int n = intervals.length;
     int choose = 1;
     int right = intervals[0][1];
     for(int i = 1; i < n; i++) {
         if(intervals[i][0] >= right) {
             right = intervals[i][1];
             choose++;
         }
     }
     return n - choose;
 }

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

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

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

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

方法：贪心

如何确保在最左边气球被引爆的情况下，尽可能多地同时引爆其他气球呢？只要将箭沿着第一个气球最右边射出即可。

所以我们的贪心算法如下：

• 将所有气球按照右端点从小到大排序；
• 将箭沿着第一个气球的最右端射出，然后移除所有被引爆的气球；
• 问题变成了原问题的子问题，重复上述操作。当所有气球被引爆时，即可求出箭的数量。

具体到代码编写上，使用一个 burst 数组来保存每个气球是否已被引爆，在发射一支箭后，遍历所有未被引爆的气球，检查是否可被引爆，是则在 burst 数组中将其标记为 true。

那么对于每一支箭，何时能确定下一支箭的位置呢？

• 把所有未引爆气球遍历完毕，然后剩余的未引爆气球中最小的右端点就是下一支箭的发射位置。但是这种方式效率很低，因为如果很多气球没有重叠，那么每一支箭仍要遍历所有气球，时间复杂度是 \(O(n^2)\)。
• 为了优化，我们不必将所有未引爆气球遍历一遍，只要碰到一个气球的左端点在当前这只箭的右边，就可以停止这一轮遍历了。然后将这只气球的右端点作为下一支箭的发射位置。因为即使后面仍有气球可以被第一支箭引爆，它仍然可以被第二支箭引爆。这样，时间复杂度是 \(O(n)\)。

写法一：明确地创建一个状态数组 shooted

public int findMinArrowShots(int[][] points) {
    // 根据右端点从小到大排序
    Arrays.sort(points, new Comparator<int[]>() {
        public int compare(int[] a, int[] b) {
            return Integer.compare(a[1], b[1]);
        }
    });
    int n = points.length;
    boolean[] shooted = new boolean[n];
    int arrowNum = 0;
    for (int i = 0; i < n; i++) {
        if (shooted[i]) continue;
        // 沿着当前气球的右端射出一支箭
        int right = points[i][1];
        arrowNum++;
        shooted[i] = true;
        for (int j = i + 1; j < n; j++) {
            if (points[j][0] <= right) shooted[j] = true;
            else break;
        }
    }
    return arrowNum;
}

写法二：只关心每一支箭的位置

 int findArrowShots(int[][] points) {
     Arrays.sort(points, new Comparator<int[]>() {
         public int compare(int[] a, int[] b) {
             return Integer.compare(a[1], b[1]);
         }
     });
     int pos = points[0][1]; // 第一支箭的位置
     int result = 1;
     // 遍历每一个气球，实时更新下一支箭的位置
     for(int[] interval : points) {
         if(interval[0] > pos) {
             pos = interval[1];
             result++;
         }
     }
     return result;
 }

注意：上述对 compare 方法的定义，会在 [[-2147483646,-2147483645],[2147483646,2147483647]] 用例上失败。所以不能直接相减，而直接比较大小：

 public int compare(int[] a, int[] b) {
     if(a[1] < b[1]) return -1;
     if(a[1] > b[1]) return 1;
     return 0;
 }
// 或者使用 Integer.compare(a[1], b[1])

763. 划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

方法：贪心

同一个字母只能出现在一个片段中，说明一个字母最初出现的位置和最后出现的位置要在同一个片段中。所以首先需要遍历字符串，统计每个字符最后出现的位置。

然后再次遍历字符串，维护当前片段的开始和结束位置 start, end ：

• 初始状态下 start = end = 0 ；
• 对于 end 之前的每个字母 c，更新 end = max(end, last[c]) ；
• 如果遍历到了边界位置 i == end ，说明完整找到了一个片段，这个片段的长度为 end - start + 1 。然后令 start = end + 1 ，（ end 会在步骤 2 中自动更新），开始寻找下一个片段。直到遍历完成整个字符串。

public List<Integer> partitionLabels(String s) {
    int n = s.length();
    // 记录每个字母最后一次出现的位置
    int[] last = new int[26];
    for (int i = 0; i < n; i++) {
        last[s.charAt(i) - 'a'] = i; 
    }
    // 遍历寻找每个片段
    List<Integer> result = new ArrayList<>();
    int start = 0, end = 0;
    for (int i = 0; i < n; i++) {
        end = Math.max(end, last[s.charAt(i) - 'a']);
        if (i == end) {
            result.add(end - start + 1);
            start = i + 1;
        }
    }
    return result;
}

56. 合并区间

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

方法：贪心

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, new Comparator<int[]>(){
        public int compare(int[] a, int[] b) {
            return a[0] - b[0];
        }
    });
    List<int[]> resultList = new ArrayList<>();
    for (int i = 0; i < intervals.length; i++) {
        int curLeft = intervals[i][0], curRight = intervals[i][1];
        // 有交集
        if (resultList.size() > 0 
                && resultList.get(resultList.size() - 1)[1] >= curLeft) {
            resultList.get(resultList.size() - 1)[1] = Math.max(
                curRight, resultList.get(resultList.size()-1)[1]); // 更新右边界
        } else { // 没有交集
            resultList.add(intervals[i]);
        }
    }
    return resultList.toArray(new int[resultList.size()][]);
}

738. 单调递增的数字

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

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

示例 :

输入: n = 332
输出: 299

方法：贪心

要尽可能大，就要尽量保持高位不变，改变低位。从高位到低位找到第一个满足 str[i] > str[i+1] 的位置 i ，将它减一，然后把后面的所有位都变成 9 就可以得到目标值。

例如：

n   = 2343
res = 2339

但是位置 i 减小 1 之后可能会使得 i 位的数字小于 i-1 位的数字（减小前两位上的数字相等），所以还要继续向高位寻找这个目标位，例如：

n   = 23332
res = 22999

这就需要在找到前面所说的 i 之后，继续向高位，找到和它连续相等的最高位，将这个最高位作为最终的目标位 ，将它减一，将它后面的所有位变成 9 。

也就是说，目标位就是第一个上到坡顶的那个元素，遍历数组，记录最大值首次出现的位置，那么条件 str[i] > str[i+1] 出现时的那个最大值就是目标值。

public int monotoneIncreasingDigits(int n) {
    char[] str = Integer.toString(n).toCharArray();
    int indexOfMax = -1;
    int maxVal = -1;
    for (int i = 0; i < str.length - 1; i++) {
        // 找到第一个上到坡顶的元素（递增-持平-递减）
        if (maxVal < str[i]) {
            maxVal = str[i];
            indexOfMax = i;
        } 
        if (str[i] > str[i+1]) { // 下坡
            str[indexOfMax] -= 1;
            for (int j = indexOfMax + 1; j < str.length; j++)
                str[j] = '9';
            break;
        }
    }
    return Integer.parseInt(new String(str));
}

标签：12,return,nums,int,++,数组,LeetCode,dp,贪心
From： https://www.cnblogs.com/lzh1995/p/16755884.html