shelterofly

目标

给你一个长度为 n 的数组 happiness ，以及一个 正整数 k 。

n 个孩子站成一队，其中第 i 个孩子的 幸福值 是 happiness[i] 。你计划组织 k 轮筛选从这 n 个孩子中选出 k 个孩子。

在每一轮选择一个孩子时，所有 尚未 被选中的孩子的 幸福值 将减少 1 。注意，幸福值 不能 变成负数，且只有在它是正数的情况下才会减少。

选择 k 个孩子，并使你选中的孩子幸福值之和最大，返回你能够得到的 最大值 。

示例 1：

输入：happiness = [1,2,3], k = 2
输出：4
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 3 的孩子。剩余孩子的幸福值变为 [0,1] 。
- 选择幸福值为 1 的孩子。剩余孩子的幸福值变为 [0] 。注意幸福值不能小于 0 。
所选孩子的幸福值之和为 3 + 1 = 4 。

示例 2：

输入：happiness = [1,1,1,1], k = 2
输出：1
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 1 的任意一个孩子。剩余孩子的幸福值变为 [0,0,0] 。
- 选择幸福值为 0 的孩子。剩余孩子的幸福值变为 [0,0] 。
所选孩子的幸福值之和为 1 + 0 = 1 。

示例 3：

输入：happiness = [2,3,4,5], k = 1
输出：5
解释：按以下方式选择 1 个孩子：
- 选择幸福值为 5 的孩子。剩余孩子的幸福值变为 [1,2,3] 。
所选孩子的幸福值之和为 5 。

说明：

• 1 <= n == happiness.length <= 2 * 10^5
• 1 <= happiness[i] <= 10^8
• 1 <= k <= n

思路

n 个孩子站成一排，happiness[i] 表示第 i 个孩子的幸福值，从中选 k 个孩子，每选择一个孩子，剩余孩子的幸福值会减少 1（但不会是负值），求所选孩子幸福值之和的最大值。

贪心策略，优先选幸福值最大的，因为下限为 0，如果放后面选减的更多。

代码

/**
 * @date 2025-12-25 8:51
 */
public class MaximumHappinessSum3075 {

    public long maximumHappinessSum(int[] happiness, int k) {
        long res = 0;
        int sub = 0;
        Arrays.sort(happiness);
        int n = happiness.length;
        for (int i = n - 1; sub < k; i--) {
            res += Math.max(0, happiness[i] - sub++);
        }
        return res;
    }
}

性能

目标

给你一个下标从 0 开始的二维整数数组 events ，其中 events[i] = [startTimei, endTimei, valuei] 。第 i 个活动开始于 startTimei ，结束于 endTimei ，如果你参加这个活动，那么你可以得到价值 valuei 。你 最多 可以参加 两个时间不重叠 活动，使得它们的价值之和 最大 。

请你返回价值之和的 最大值 。

注意，活动的开始时间和结束时间是 包括 在活动时间内的，也就是说，你不能参加两个活动且它们之一的开始时间等于另一个活动的结束时间。更具体的，如果你参加一个活动，且结束时间为 t ，那么下一个活动必须在 t + 1 或之后的时间开始。

示例 1:

输入：events = [[1,3,2],[4,5,2],[2,4,3]]
输出：4
解释：选择绿色的活动 0 和 1 ，价值之和为 2 + 2 = 4 。

示例 2：

输入：events = [[1,3,2],[4,5,2],[1,5,5]]
输出：5
解释：选择活动 2 ，价值和为 5 。

示例 3：

输入：events = [[1,5,3],[1,5,1],[6,6,5]]
输出：8
解释：选择活动 0 和 2 ，价值之和为 3 + 5 = 8 。

说明：

• 2 <= events.length <= 10^5
• events[i].length == 3
• 1 <= startTimei <= endTimei <= 10^9
• 1 <= valuei <= 10^6

思路

有一个二维数组 events，events[i] 表示事件 i 的 (开始时间，结束时间，价值) 三元组，至多参加两个活动，这两个活动不能重叠 (结束时间与开始时间也不能重叠)，求参加活动的最大价值。

根据开始时间排序，二分查找第一个大于结束时间的下标，维护后缀最大值。

代码

/**
 * @date 2025-12-23 8:53
 */
public class MaxTwoEvents2054 {

    public int maxTwoEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        int res = 0;
        int n = events.length;
        int[] suffix = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffix[i] = Math.max(suffix[i + 1], events[i][2]);
        }
        for (int[] event : events) {
            int index = bs(events, event[1]);
            res = Math.max(res, event[2] + suffix[index]);
        }
        return res;
    }

    public int bs(int[][] events, int target) {
        int l = 0;
        int r = events.length - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (events[m][0] <= target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return l;
    }

}

性能

目标

给定由 n 个字符串组成的数组 strs，其中每个字符串长度相等。

选取一个删除索引序列，对于 strs 中的每个字符串，删除对应每个索引处的字符。

比如，有 strs = ["abcdef", "uvwxyz"]，删除索引序列 {0, 2, 3}，删除后 strs 为["bef", "vyz"]。

假设，我们选择了一组删除索引 answer，那么在执行删除操作之后，最终得到的数组的元素是按 字典序（strs[0] <= strs[1] <= strs[2] ... <= strs[n - 1]）排列的，然后请你返回 answer.length 的最小可能值。

示例 1：

输入：strs = ["ca","bb","ac"]
输出：1
解释： 
删除第一列后，strs = ["a", "b", "c"]。
现在 strs 中元素是按字典排列的 (即，strs[0] <= strs[1] <= strs[2])。
我们至少需要进行 1 次删除，因为最初 strs 不是按字典序排列的，所以答案是 1。

示例 2：

输入：strs = ["xc","yb","za"]
输出：0
解释：
strs 的列已经是按字典序排列了，所以我们不需要删除任何东西。
注意 strs 的行不需要按字典序排列。
也就是说，strs[0][0] <= strs[0][1] <= ... 不一定成立。

示例 3：

输入：strs = ["zyx","wvu","tsr"]
输出：3
解释：
我们必须删掉每一列。

说明：

• n == strs.length
• 1 <= n <= 100
• 1 <= strs[i].length <= 100
• strs[i] 由小写英文字母组成

思路

有一个元素长度相同的字符串数组 strs，通过删除列使得字符串元素按字典序非严格递增，返回删除的最少列数。

首先如果按列不是非严格递增的，那么一定要删除该列。然后，如果是非严格递增的，需要继续考查相同行后续列的字典序。

维护同一列中相同字母的行标列表 sameList，初始时包括所有行，如果需要删除就直接进入下一列循环，否则遍历 sameList 判断是否是升序（相同的字母组内比较），同时记录当前列相同的行标，如果 sameList 列表为空则退出。

代码

/**
 * @date 2025-12-21 19:24
 */
public class MinDeletionSize955 {

    public int minDeletionSize(String[] strs) {
        int n = strs.length;
        int m = strs[0].length();
        List<Integer> indexList = new ArrayList<>(n);
        for (int i = 0; i < n - 1; i++) {
            indexList.add(i);
        }
        int res = 0;
        here:
        for (int i = 0; i < m; i++) {
            if (indexList.size() == 0) {
                break;
            }
            List<Integer> tmp = new ArrayList<>();
            for (Integer k : indexList) {
                char cur = strs[k].charAt(i);
                char next = strs[k + 1].charAt(i);
                if (cur > next) {
                    res++;
                    continue here;
                } else if (cur == next) {
                    tmp.add(k);
                }
            }
            indexList = tmp;
        }
        return res;
    }

}

性能

目标

给你两个整数数组 prices 和 strategy，其中：

• prices[i] 表示第 i 天某股票的价格。
• strategy[i] 表示第 i 天的交易策略，其中：
  • -1 表示买入一单位股票。
  • 0 表示持有股票。
  • 1 表示卖出一单位股票。

同时给你一个 偶数 整数 k，你可以对 strategy 进行 最多一次 修改。一次修改包括：

• 选择 strategy 中恰好 k 个 连续 元素。
• 将前 k / 2 个元素设为 0（持有）。
• 将后 k / 2 个元素设为 1（卖出）。

利润 定义为所有天数中 strategy[i] * prices[i] 的 总和 。

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

注意： 没有预算或股票持有数量的限制，因此所有买入和卖出操作均可行，无需考虑过去的操作。

示例 1：

输入： prices = [4,2,8], strategy = [-1,0,1], k = 2
输出： 10
解释：
修改 策略 利润计算 利润
原始 [-1, 0, 1] (-1 × 4) + (0 × 2) + (1 × 8) = -4 + 0 + 8 4
修改 [0, 1] [0, 1, 1] (0 × 4) + (1 × 2) + (1 × 8) = 0 + 2 + 8 10
修改 [1, 2] [-1, 0, 1] (-1 × 4) + (0 × 2) + (1 × 8) = -4 + 0 + 8 4
因此，最大可能利润是 10，通过修改子数组 [0, 1] 实现。

示例 2：

输入： prices = [5,4,3], strategy = [1,1,0], k = 2
输出： 9
解释：
修改 策略 利润计算 利润
原始 [1, 1, 0] (1 × 5) + (1 × 4) + (0 × 3) = 5 + 4 + 0 9
修改 [0, 1] [0, 1, 0] (0 × 5) + (1 × 4) + (0 × 3) = 0 + 4 + 0 4
修改 [1, 2] [1, 0, 1] (1 × 5) + (0 × 4) + (1 × 3) = 5 + 0 + 3 8
因此，最大可能利润是 9，无需任何修改即可达成。

说明：

• 2 <= prices.length == strategy.length <= 10^5
• 1 <= prices[i] <= 10^5
• -1 <= strategy[i] <= 1
• 2 <= k <= prices.length
• k 是偶数

思路

定长滑动窗口，考虑窗口内现利润与原利润差值的最大值。维护窗口中间下标，调整后的利润从中间下标移出。使用一个变量记录窗口左端点原利润的前缀，另一个变量记录右端点的原利润前缀，相减可得窗口的原利润。原利润是根据策略累加，现利润是根据价格累加。

代码

/**
 * @date 2025-12-18 8:58
 */
public class MaxProfit3652 {

    public long maxProfit(int[] prices, int[] strategy, int k) {
        int n = prices.length;
        long cur = 0L, sum = 0L;
        for (int r = 0; r < k / 2; r++) {
            sum += prices[r] * strategy[r];
        }
        for (int r = k / 2; r < k; r++) {
            sum += prices[r] * strategy[r];
            cur += prices[r];
        }
        long diff = cur - sum;
        long prefix = 0L;
        int l = 0, m = k / 2;
        for (int r = k; r < n; r++) {
            sum += prices[r] * strategy[r];
            cur += prices[r] - prices[m++];
            prefix += prices[l] * strategy[l];
            l++;
            diff = Math.max(diff, cur - sum + prefix);
        }
        return sum + Math.max(0, diff);
    }

}

性能