2938.区分黑球与白球

目标

桌子上有 n 个球,每个球的颜色不是黑色,就是白色。

给你一个长度为 n 、下标从 0 开始的二进制字符串 s,其中 1 和 0 分别代表黑色和白色的球。

在每一步中,你可以选择两个相邻的球并交换它们。

返回「将所有黑色球都移到右侧,所有白色球都移到左侧所需的 最小步数」。

示例 1:

输入:s = "101"
输出:1
解释:我们可以按以下方式将所有黑色球移到右侧:
- 交换 s[0] 和 s[1],s = "011"。
最开始,1 没有都在右侧,需要至少 1 步将其移到右侧。

示例 2:

输入:s = "100"
输出:2
解释:我们可以按以下方式将所有黑色球移到右侧:
- 交换 s[0] 和 s[1],s = "010"。
- 交换 s[1] 和 s[2],s = "001"。
可以证明所需的最小步数为 2 。

示例 3:

输入:s = "0111"
输出:0
解释:所有黑色球都已经在右侧。

说明:

  • 1 <= n == s.length <= 10^5
  • s[i] 不是 '0',就是 '1'

思路

有一个数组,其元素值不是0就是1,现在需要将所有的1都移到右边,每一步可以选择相邻的两个元素交换其位置,问移动的最小步数。

从左向右遍历数组元素,如果值为1就累加cnt,如果值为0就将移动步数加上 cnt。简单来说就是遇到1就合并,记录其个数,遇到0就整体移动 res += cnt。每次移动都贪心地将0移至其最终位置上。

有网友提到可以使用归并排序记录逆序对。

还有网友是基于下标和计算的。因为最终0都在右边,其下标和可以通过等差数列求和得到。我们只需在遍历过程中记录0的个数,并累加0的下标,然后与最终状态的下标和相减即可。

代码

package medium;

/**
 * @date 2024-06-06 0:03
 */
public class MinimumSteps2938 {

    /**
     * 将黑球视为一个整体,遇到黑球则合并到一起增加其权重,这样就可以视为将一个带权黑球从左移到右,每一步都是必要的。
     * 这其实也算是在移动的过程中统计逆序对的个数
     */
    public long minimumSteps(String s) {
        long res = 0;
        int n = s.length();
        int i = 0;
        long cnt = 0;
        while (i < n) {
            if (s.charAt(i) == '0') {
                // 遇到0就移动  累加移动步数,可以使用双指针优化
                res += cnt;
            } else {
                // 遇到1则合并
                cnt++;
            }
            i++;
        }
        return res;
    }

    /**
     * 优化
     * 使用双指针可以减少累加次数
     */
    public long minimumSteps_v1(String s) {
        long res = 0;
        int n = s.length();
        int i = 0;
        // left指向1的位置,如果第一值是0,那么left与i一起右移
        // 如果第一个值是1,仅移动i,当遇到0时,左侧1的个数就是i-left
        // 本来从下标left到i元素个数为 i - left + 1,由于i指向的不是1,所以不用加1
        int left = 0;
        while (i < n) {
            if (s.charAt(i) == '0') {
                res += i - left;
                left++;
            }
            i++;
        }
        return res;
    }
}

性能

1953.你可以工作的最大周数

目标

给你 n 个项目,编号从 0 到 n - 1 。同时给你一个整数数组 milestones ,其中每个 milestones[i] 表示第 i 个项目中的阶段任务数量。

你可以按下面两个规则参与项目中的工作:

  • 每周,你将会完成 某一个 项目中的 恰好一个 阶段任务。你每周都 必须 工作。
  • 在 连续的 两周中,你 不能 参与并完成同一个项目中的两个阶段任务。

一旦所有项目中的全部阶段任务都完成,或者仅剩余一个阶段任务都会导致你违反上面的规则,那么你将 停止工作 。注意,由于这些条件的限制,你可能无法完成所有阶段任务。

返回在不违反上面规则的情况下你 最多 能工作多少周。

示例 1:

输入:milestones = [1,2,3]
输出:6
解释:一种可能的情形是:
​​​​- 第 1 周,你参与并完成项目 0 中的一个阶段任务。
- 第 2 周,你参与并完成项目 2 中的一个阶段任务。
- 第 3 周,你参与并完成项目 1 中的一个阶段任务。
- 第 4 周,你参与并完成项目 2 中的一个阶段任务。
- 第 5 周,你参与并完成项目 1 中的一个阶段任务。
- 第 6 周,你参与并完成项目 2 中的一个阶段任务。
总周数是 6 。

示例 2:

输入:milestones = [5,2,1]
输出:7
解释:一种可能的情形是:
- 第 1 周,你参与并完成项目 0 中的一个阶段任务。
- 第 2 周,你参与并完成项目 1 中的一个阶段任务。
- 第 3 周,你参与并完成项目 0 中的一个阶段任务。
- 第 4 周,你参与并完成项目 1 中的一个阶段任务。
- 第 5 周,你参与并完成项目 0 中的一个阶段任务。
- 第 6 周,你参与并完成项目 2 中的一个阶段任务。
- 第 7 周,你参与并完成项目 0 中的一个阶段任务。
总周数是 7 。
注意,你不能在第 8 周参与完成项目 0 中的最后一个阶段任务,因为这会违反规则。
因此,项目 0 中会有一个阶段任务维持未完成状态。

说明:

  • n == milestones.length
  • 1 <= n <= 10^5
  • 1 <= milestones[i] <= 10^9

思路

给定一个数组,其元素值表示项目的任务数,每一周可以完成任一项目的一个任务,不能连续两周完成同一项目的任务,即每完成一个任务必须切换项目,问最多能完成多少任务。

观察上面的示例发现不能优先选择任务数少的项目,因为任务少的项目先完成后,任务多的项目可能由于没有项目切换被剩下。

刚开始的想法就是先从小到大排序,将个项目的任务数放入优先队列,然后每次从最大与次最大的项目中选取任务,提交之后提示超时。

然后想到没必要一次只减1,于是就直接从最大中减去次最大 next,然后累加 2 * next,提交之后发现对于max == next 时会给出错误答案,于是就记录最大值相同的个数 times,后面累加next * (times + 1) 即可。提交之后发现下面的案例给出的答案不对:

正确的处理过程可以是每次取最大与次最大:

task1:8 task2:6 task3:4 cost
7 5(end) 4 2
6 4(end) 4 2
5 3(end) 4 2
4 3 3(end) 2
3 2(end) 3 2
2 2 2(end) 2
1 1 1(end) 3
0 0 0(end) 3
- - - 合计:18

而提交的算法是这样处理的,违背了上面的处理原则。

task1:8 task2:6 task3:4 cost
2 0(end) 4 12
0(end) 0 2 4
0 0 1 1
- - - 合计:17

如果考虑第三大元素 third,一次性只减到 third,累加 2 * (next - third) 的话,后续还是要一个一个算。

task1:8 task2:6 task3:4 cost
6 4(end) 4 2
5 3(end) 4 2
4 3 3(end) 2
3 2(end) 3 2
2 2 2(end) 2
1 1 1(end) 3
0 0 0(end) 3
- - - 合计:18

然后还发现对于某些例子是能够计算出正确结果的,例如

task1:5 task2:2 task3:1 cost
3 0(end) 1 4
2 0 0(end) 2
1(end) 0 0 1
- - - 合计:7

于是发现,只要除了最大值其余元素和只要大于等于最大值就可以全部完成。

贪心算法难想,难证明,大多凭直觉,没有通用性。我没有想到这个结论竟然可以推广到多个元素的情况。感觉有点像脑筋急转弯,想通了就很简单。

考虑下面的例子:

最大值每减1,后面的元素都可以同步的减1。

8 8 8 8 8
7 7 7 7 7
......
0 0 0 0 0 
----------------

这个就不能同步减了,否则最大值消不完

8 4 3 2 1
7 3 3 2 1
6 2 3 2 1
5 2 2 2 1
4 1 2 2 1
3 1 1 2 1
2 1 1 1 1
1 1 1 1 0
0 0 0 0 0

可以想象成两个柱子,最大的是一个柱子,其余的垒成一个柱子,如果大于最大的柱子就截断,作为新的柱子如果还大接着截,不能超过最大的柱子。极端的情况就是全相同,可以全部完成。只要保证有一个柱子与最大的柱子一样高就可以来回切换来完成全部任务。而如果其余的柱子垒起来没有最大的高,那么只能完成 其余之和*2+1

代码

package medium;

/**
 * @date 2024-05-16 8:37
 */
public class NumberOfWeeks1953 {

    /**
     * 执行通过
     * 如果最大的小于等于其余之和,那么所有任务均可完成
     * 如果最大的大于其余之和,那么可以完成其余之和*2+1
     */
    public long numberOfWeeks_v2(int[] milestones) {
        long sum = 0;
        int max = 0;
        for (int milestone : milestones) {
            if (milestone > max) {
                max = milestone;
            }
            sum += milestone;
        }
        long remainder = sum - max;
        return remainder < max ? remainder * 2 + 1 : sum;
    }

    /**
     * 这个算法是调试出来的
     */
    public long numberOfWeeks_v1(int[] milestones) {
        long res = 0;
        PriorityQueue<Integer> q = new PriorityQueue<>(Comparator.reverseOrder());
        for (int milestone : milestones) {
            q.offer(milestone);
        }
        while (!q.isEmpty()) {
            int head = q.poll();
            // 输入数组中的值均大于0,res放在这里加,以免漏掉最后一个
            res++;
            if (q.isEmpty()) {
                // 如果后面没有任务,连续两周完成同一项目的任务会违反规则,直接返回
                return res;
            }
            int next = q.poll();
            int times = 1;
            while (!q.isEmpty() && next == head) {
                times++;
                next = q.poll();
            }
            if (q.size() == 1 && q.peek() + next > head) {
                // 处理最后三个,如果其余两个大于最大值就返回它们的和,减1是因为为了防止漏掉最后一个加了1
                return res + head * times + next + q.poll() - 1;
            }
            res += (long) next * (times + 1) - 1;
            head -= next;
            if (head > 0) {
                for (int i = 0; i < times; i++) {
                    q.offer(head);
                }
            }
        }
        return res;
    }

性能

方法一

方法二

2244.完成所有任务需要的最少轮数

目标

给你一个下标从 0 开始的整数数组 tasks ,其中 tasks[i] 表示任务的难度级别。在每一轮中,你可以完成 2 个或者 3 个 相同难度级别 的任务。

返回完成所有任务需要的 最少 轮数,如果无法完成所有任务,返回 -1 。

示例 1:

输入:tasks = [2,2,3,3,2,4,4,4,4,4]
输出:4
解释:要想完成所有任务,一个可能的计划是:
- 第一轮,完成难度级别为 2 的 3 个任务。 
- 第二轮,完成难度级别为 3 的 2 个任务。 
- 第三轮,完成难度级别为 4 的 3 个任务。 
- 第四轮,完成难度级别为 4 的 2 个任务。 
可以证明,无法在少于 4 轮的情况下完成所有任务,所以答案为 4 。

示例 2:

输入:tasks = [2,3,3]
输出:-1
解释:难度级别为 2 的任务只有 1 个,但每一轮执行中,只能选择完成 2 个或者 3 个相同难度级别的任务。因此,无法完成所有任务,答案为 -1 。

说明:

  • 1 <= tasks.length <= 10^5
  • 1 <= tasks[i] <= 10^9

思路

有一个任务数组,元素值表示任务级别,现在需要我们完成任务,每一轮只能完成2个或3个相同级别的任务,问完成所有任务最少需要多少轮,如果无法完成所有任务返回-1。

首先统计序列中等级相同的任务个数,可以使用哈希表,也可以先排序再在循环的过程中使用滑动窗口统计(这个效率最高,但是容易出错)。然后:

  • 如果序列中只有1个同级别任务,那么无法完成,返回-1。
  • 如果序列中有2个同级别任务,累加1。
  • 如果序列中有3个同级别任务,累加1。
  • 如果序列中同级别任务数 n 大于3,累加 (n + 2)/3 向下取整
    • n % 3 == 1,这时只需将之前3个一组的任务与余下的1个任务组合,然后拆成2组即可:loop = (n - 4)/3 + 2 = (n + 2)/3
    • n % 3 == 2,多余的两个自成一组:loop = (n -2)/3 + 1 = (n + 1)/3。这时 (n+1) 刚好可以被3整除,(n+2)/3 向下取整不会影响结果。
    • n % 3 == 0,直接整除即可:loop = n/3。道理同上。

以上就是贪心策略,每次取尽可能多的任务。

代码

/**
 * @date 2024-05-14 0:11
 */
public class MinimumRounds2244 {
    public int minimumRounds(int[] tasks) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int t : tasks) {
            map.merge(t, 1, Integer::sum);
        }
        for (Integer cnt : map.values()) {
            if (cnt == 1) {
                return -1;
            } else if (cnt == 2 || cnt == 3) {
                res++;
            } else if (cnt % 3 == 0) {
                res += cnt / 3;
            } else if (cnt % 3 == 2) {
                res += (cnt - 2) / 3 + 1;
            } else if (cnt % 3 == 1) {
                res += (cnt - 4) / 3 + 2;
            }
        }
        return res;
    }
}

性能

1702.修改后的最大二进制字符串

目标

给你一个二进制字符串 binary ,它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改:

  • 操作 1 :如果二进制串包含子字符串 "00" ,你可以用 "10" 将其替换。

    比方说, "00010" -> "10010"

  • 操作 2 :如果二进制串包含子字符串 "10" ,你可以用 "01" 将其替换。

    比方说, "00010" -> "00001"

请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 x 对应的十进制数字大于二进制字符串 y 对应的十进制数字,那么我们称二进制字符串 x 大于二进制字符串 y 。

示例 1:

输入:binary = "000110"
输出:"111011"
解释:一个可行的转换为:
"000110" -> "000101" 
"000101" -> "100101" 
"100101" -> "110101" 
"110101" -> "110011" 
"110011" -> "111011"

示例 2:

输入:binary = "01"
输出:"01"
解释:"01" 没办法进行任何转换。

说明:

  • 1 <= binary.length <= 10^5
  • binary 仅包含 '0' 和 '1'

思路

看到这道题我最先想到的是使用字符串替换,先把00的都替换为10,直到不能替换为止。然后再替换10为01,直到不能替换为止。然后再从头替换,相当于是一个while里面套两个while。

通过对具体例子的观察可以发现将10替换为01不是无条件的,我甚至还写了比较字符串大小的方法,如果字符串变小了就不变了。但其实是不行的,因为中间过程确实存在变小的情况。

最后经过观察分析发现必须要前面有0才可以替换,因为这样可以将高位的0置为1。以01110为例,最后能够转换为10111。

于是就想通过replace方法替换捕获组来实现,例如匹配 0(1*)0,替换为 10(匹配到的1),试了一下发现replacement不支持。Pattern 类也是无法使用的。

基于上面的分析,我们可以通过算法模拟出替换过程,这里面需要用到双指针 starti

  1. 如果 starti 相同且都指向1,那么直接跳过
  2. 如果 starti 相差1,且 i 指向0,即00的情况,那么将 start 指向置1,start++
  3. 否则,如果 starti 相差大于1,且 i 指向0,即0(1+)0的情况,那么需要将start 指向置1,start 后面的置0,i 指向的置1 即可

需要注意的是,如果 starti 不同,那么 start 指向的一定是0。其实步骤2与3可以合并,只需先将 i 置1,然后再将 start 后面的置0即可。

看了官网的题解,还提供了一种直接构建的算法。

如果字符串中有多个0,总可以将它们通过10->01将其前移至第一个0的位置,然后通过00->10,使高位的0变为1。最终的结果中至多包含1个0。

因此,直接构建的方法是:从第一个0开始,后面的0全置为1,然后将第一个0后移 0的个数减1 个位置。

代码

/**
 * @date 2024-04-10 0:53
 */
public class MaximumBinaryString1702 {

    /** 直接构造 */
    public String maximumBinaryString_v2(String binary) {
        char[] b = binary.toCharArray();
        int firstZero = binary.indexOf('0');
        if (firstZero == -1) {
            return binary;
        }
        int cnt = 0;
        for (int i = firstZero; i < b.length; i++) {
            cnt += '1' - b[i];
            b[i] = '1';
        }
        b[firstZero + cnt - 1] = '0';
        return new String(b);
    }

    public String maximumBinaryString_v1(String binary) {
        char[] b = binary.toCharArray();
        int start = 0;
        for (int i = 0; i < b.length; i++) {
            if (start == i && '1' == b[i]) {
                start++;
            } else if (start <= i - 1 && '0' == b[i]) {
                b[start++] = '1';
                b[i] = '1';
                b[start] = '0';
            }
        }
        return new String(b);
    }

    public String maximumBinaryString(String binary) {
        char[] b = binary.toCharArray();
        int start = 0;
        for (int i = 0; i < b.length; i++) {
            if (start == i && '1' == b[i]) {
                start++;
            } else if (start == i - 1 && '0' == b[i]) {
                b[start++] = '1';
            } else if (start < i - 1 && '0' == b[i]) {
                b[start++] = '1';
                b[start] = '0';
                b[i] = '1';
            }
        }
        return new String(b);
    }

}

性能

2789.合并后数组中的最大元素

目标

给你一个下标从 0 开始、由正整数组成的数组 nums 。

你可以在数组上执行下述操作 任意 次:

  • 选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的整数 i 。将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ,并从数组中删除元素 nums[i] 。

返回你可以从最终数组中获得的 最大 元素的值。

示例 1:

输入:nums = [2,3,7,9,3]
输出:21
解释:我们可以在数组上执行下述操作:
- 选中 i = 0 ,得到数组 nums = [5,7,9,3] 。
- 选中 i = 1 ,得到数组 nums = [5,16,3] 。
- 选中 i = 0 ,得到数组 nums = [21,3] 。
最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。

示例 2:

输入:nums = [5,3,3]
输出:11
解释:我们可以在数组上执行下述操作:
- 选中 i = 1 ,得到数组 nums = [5,6] 。
- 选中 i = 0 ,得到数组 nums = [11] 。
最终数组中只有一个元素,即 11 。

说明:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

思路

这个题要我们对一个数组进行操作并返回最大的元素值。这里的操作指的是合并相邻的非严格递增元素。

刚开始没有头绪,如果真的按照操作步骤先把符合条件的值求出来,替换掉较大元素的值并删掉较小元素,那么就需要频繁地移动数组数据。

除此之外需要考虑一个重要的问题,如何合并才能使最终的结果最大?如果从前向后合并,比如 [2,6,7] 先合并前两个得到[8,7]肯定没有从后向前合并得到的值 [2, 13] [15] 大。是否存在那种先从前向后合并,然后再从后向前合并才能得到最大值的情况?

刚开始是不那么容易弄清的。也考虑过优先合并 后面的元素值 比 合并后的元素值 大的 元素,提前考虑了一步能否避免上面的情况?好像可以,因为操作没有破坏原数组能否合并的状态。那么这种操作需要循环几次?时间复杂度是O(n)~O(nlogn)吗?

[1,2,1,4,1,2,1,4]一次遍历后可以变为[3,5,3,5],然后再遍历一次得到 [8, 8],再来一次 [16],即O(nlogn)。更好的情况就是递增序列O(n)。

经过上面的分析可以发现,优先使后面的元素最大才能得到最大值。那么为什么不从后向前遍历并累加呢?如果遇到一个元素的值比后面所有元素的累加和还要大,那不管前面怎么操作,由于元素都是正整数,合并后只会更大。

想清楚了这一点就非常简单了。

代码

/**
 * @date 2024-03-14 11:29
 */
public class MaxArrayValue {

    public long maxArrayValue(int[] nums) {
        long res = nums[nums.length - 1];
        for (int i = nums.length - 1; i >= 1; i--) {
            res = res >= nums[i - 1] ? res + nums[i - 1] : nums[i - 1];
        }
        return res;
    }

    public static void main(String[] args) {
        MaxArrayValue main = new MaxArrayValue();
//        int[] nums = new int[]{2, 3, 7, 9, 3};
//        int[] nums = new int[]{5, 3, 3};
//        int[] nums = new int[]{77};
        int[] nums = new int[]{34, 95, 50, 12, 25, 100, 21, 3, 25, 16, 76, 73, 93, 46, 18};
        System.out.println(main.maxArrayValue(nums));
    }
}

性能

2673.使二叉树所有路径值相等的最小代价

目标

给你一个整数 n 表示一棵 满二叉树 里面节点的数目,节点编号从 1 到 n 。根节点编号为 1 ,树中每个非叶子节点 i 都有两个孩子,分别是左孩子 2 i 和右孩子 2 i + 1 。

树中每个节点都有一个值,用下标从 0 开始、长度为 n 的整数数组 cost 表示,其中 cost[i] 是第 i + 1 个节点的值。每次操作,你可以将树中 任意 节点的值 增加 1 。你可以执行操作 任意 次。

你的目标是让根到每一个 叶子结点 的路径值相等。请你返回 最少 需要执行增加操作多少次。

注意:

  • 满二叉树 指的是一棵树,它满足树中除了叶子节点外每个节点都恰好有 2 个子节点,且所有叶子节点距离根节点距离相同。
  • 路径值 指的是路径上所有节点的值之和。

说明:

  • 3 <= n <= 105
  • n + 1 是 2 的幂
  • cost.length == n
  • 1 <= cost[i] <= 104

思路

操作首先要知道操作的最终状态:各路径相等。那么哪一个路径值可以使操作总数最小?既然明确不了哪一个路径又如何操作,又怎会知道最小?最开始以为可能是路径的中位数,但是我也没法证明。后来发现想复杂了,操作只能加不能减,那么问题就变成了将所有路径变成最大最少需要几次操作。

首先可以根据节点的父子关系将子路径值层层累加,那么最底下的叶子层就是各条路径的值。用最大路径值分别减去其它路径值得到相应的操作数,但这时操作数不是最小的。注意到,如果左右孩子所需操作均不为零,可以将较小孩子节点的操作数提到父节点上,并将操作数置零,而另一个孩子节点同时减去该操作数,这样就完成了一步最小化。依次向上计算,直到根节点,然后统计各节点操作数即可。

代码

/**
 * @date 2024-02-28 8:52
 */
public class MinIncrements {

    public int minIncrements(int n, int[] cost) {
        for (int i = 1; i < cost.length; i++) {
            if (i % 2 == 1) {
                cost[i] += cost[(i - 1) / 2];
            } else {
                cost[i] += cost[(i - 2) / 2];
            }
        }
        int max = 0;
        double l = Math.floor(Math.log(Double.parseDouble(String.valueOf(n))) / Math.log(2.0));
        for (int i = (int) Math.pow(2.0, l) - 1; i < cost.length; i++) {
            if (cost[i] > max) {
                max = cost[i];
            }
        }
        for (int i = (int) Math.pow(2.0, l) - 1; i < cost.length; i++) {
            cost[i] = max - cost[i];
        }
        for (int i = cost.length - 1; i > 2; i -= 2) {
            if (cost[i] == 0 || cost[i - 1] == 0) {
                cost[(i - 2) / 2] = 0;
                continue;
            }
            if (cost[i] <= cost[i - 1]) {
                cost[(i - 2) / 2] = cost[i];
                cost[i - 1] = cost[i - 1] - cost[i];
                cost[i] = 0;
            } else if (cost[i] >= cost[i - 1]) {
                cost[(i - 2) / 2] = cost[i - 1];
                cost[i] = cost[i] - cost[i - 1];
                cost[i - 1] = 0;
            }
        }
        int res = 0;
        for (int i = 1; i < cost.length; i++) {
            res += cost[i];
        }
        return res;
    }

    public static void main(String[] args) {

        MinIncrements main = new MinIncrements();
//        int[] cost = new int[]{1, 5, 2, 2, 3, 3, 1};
        int[] cost = new int[]{764, 1460, 2664, 764, 2725, 4556, 5305, 8829, 5064, 5929, 7660, 6321, 4830, 7055, 3761};
        System.out.println(main.minIncrements(cost.length, cost));
    }
}

性能

又是勉强过关。看看官网给的答案:

class Solution {
    public int minIncrements(int n, int[] cost) {
        int ans = 0;
        for (int i = n - 2; i > 0; i -= 2) {
            ans += Math.abs(cost[i] - cost[i + 1]);
            // 叶节点 i 和 i+1 的双亲节点下标为 i/2(整数除法)
            cost[i / 2] += Math.max(cost[i], cost[i + 1]);
        }
        return ans;
    }
}

称之为自底向上的贪心算法。所谓贪心算法,它在每一步都做出当时看起来最佳的选择,也就是说,它总是做出局部最优的选择。贪心算法并不保证得到最优解,但对很多问题确实可以求得最优解。