作者： admin

目标

给你一个下标从 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);
    }

}

性能

目标

给你一个整数数组 prices ，表示一支股票的历史每日股价，其中 prices[i] 是这支股票第 i 天的价格。

一个 平滑下降的阶段 定义为：对于 连续一天或者多天 ，每日股价都比 前一日股价恰好少 1 ，这个阶段第一天的股价没有限制。

请你返回 平滑下降阶段 的数目。

示例 1：

输入：prices = [3,2,1,4]
输出：7
解释：总共有 7 个平滑下降阶段：
[3], [2], [1], [4], [3,2], [2,1] 和 [3,2,1]
注意，仅一天按照定义也是平滑下降阶段。

示例 2：

输入：prices = [8,6,7,7]
输出：4
解释：总共有 4 个连续平滑下降阶段：[8], [6], [7] 和 [7]
由于 8 - 6 ≠ 1 ，所以 [8,6] 不是平滑下降阶段。

示例 3：

输入：prices = [1]
输出：1
解释：总共有 1 个平滑下降阶段：[1]

说明：

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

思路

求满足要求的子数组个数，要求子数组严格单调递减且相邻元素差为 1。

枚举右端点 r，假设满足条件的最小的左端点为 l，那么以 r 为右端点且满足条件的子数组个数为 r - l + 1。对于每一个 r，无需重复判断最小的 l，它可以从前一个状态转移过来，即如果 prices[r - 1] - prices[r] == 1 那么 l 仍是以 r - 1 为右端点且满足条件的最小左端点，否则 l = r。

代码

/**
 * @date 2025-12-15 9:10
 */
public class GetDescentPeriods2110 {

    public long getDescentPeriods(int[] prices) {
        long res = 0L;
        int l = 0;
        int n = prices.length;
        int prev = prices[0] + 1;
        for (int r = 0; r < n; r++) {
            if (prev - prices[r] != 1){
                l = r;
            }
            res += r - l + 1;
            prev = prices[r];
        }
        return res;
    }
}

性能