标签： 滑动窗口

目标

给你两个整数数组 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;
    }
}

性能

目标

给你一个整数数组 nums 和一个整数 k。你的任务是将 nums 分割成一个或多个 非空 的连续子段，使得每个子段的 最大值 与 最小值 之间的差值 不超过 k。

返回在此条件下将 nums 分割的总方法数。

由于答案可能非常大，返回结果需要对 10^9 + 7 取余数。

示例 1：

输入： nums = [9,4,1,3,7], k = 4
输出： 6
解释：
共有 6 种有效的分割方式，使得每个子段中的最大值与最小值之差不超过 k = 4：
[[9], [4], [1], [3], [7]]
[[9], [4], [1], [3, 7]]
[[9], [4], [1, 3], [7]]
[[9], [4, 1], [3], [7]]
[[9], [4, 1], [3, 7]]
[[9], [4, 1, 3], [7]]

示例 2：

输入： nums = [3,3,4], k = 0
输出： 2
解释：
共有 2 种有效的分割方式，满足给定条件：
[[3], [3], [4]]
[[3, 3], [4]]

说明：

• 2 <= nums.length <= 5 * 10^4
• 1 <= nums[i] <= 10^9
• 0 <= k <= 10^9

思路

划分数组 nums，使得每一个子数组的最大最小值之差不超过 k，求划分的总方法数。

定义 dp[i] 表示 [0, i] 满足条件的划分数，dp[i + 1] = Σdp[j] j∈[l, i]，l 是固定右端点后满足条件的最小下标。

枚举满足条件的最小下标时可以使用滑动窗口，使用单调栈来维护窗口的最大值与最小值。

代码

/**
 * @date 2025-12-09 9:38
 */
public class CountPartitions3578 {

    public int countPartitions(int[] nums, int k) {
        Deque<Integer> max = new ArrayDeque<>();
        Deque<Integer> min = new ArrayDeque<>();
        int mod = 1000000007;
        int n = nums.length;
        long[] dp = new long[n + 1];
        dp[0] = 1;
        int l = 0;
        long window = 0;
        for (int r = 0; r < n; r++) {
            while (!max.isEmpty() && max.peekLast() < nums[r]) {
                max.pollLast();
            }
            while (!min.isEmpty() && min.peekLast() > nums[r]) {
                min.pollLast();
            }
            max.offer(nums[r]);
            min.offer(nums[r]);
            int diff = max.peek() - min.peek();

            window += dp[r];
            while (l <= r && diff > k) {
                if (max.peek() == nums[l]) {
                    max.poll();
                }
                if (min.peek() == nums[l]) {
                    min.poll();
                }
                diff = max.peek() - min.peek();
                window -= dp[l++];
            }
            dp[r + 1] = window % mod;
        }
        return (int) (dp[n] % mod);
    }

}

性能

目标

给你一个整数数组 nums 和一个整数 k 。

返回 nums 中一个 非空子数组 的 最大 和，要求该子数组的长度可以 被 k 整除。

示例 1：

输入： nums = [1,2], k = 1
输出： 3
解释：
子数组 [1, 2] 的和为 3，其长度为 2，可以被 1 整除。

示例 2：

输入： nums = [-1,-2,-3,-4,-5], k = 4
输出： -10
解释：
满足题意且和最大的子数组是 [-1, -2, -3, -4]，其长度为 4，可以被 4 整除。

示例 3：

输入： nums = [-5,1,2,-3,4], k = 2
输出： 4
解释：
满足题意且和最大的子数组是 [1, 2, -3, 4]，其长度为 4，可以被 2 整除。

说明：

• 1 <= k <= nums.length <= 2 * 10^5
• -10^9 <= nums[i] <= 10^9

思路

计算长度能被 k 整除的子数组的最大元素和。

核心点是维护同余前缀和的最小值。

也有网友使用滑窗加动态规划来做，滑窗计算 长度为 k 的子数组和，动态规划累加长度 m * k 的子数组和，这里使用了贪心策略，如果前面的子数组和小于 0，直接重置为 0。

代码

/**
 * @date 2025-11-27 9:06
 */
public class MaxSubarraySum3381 {

    public long maxSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
        long[] minPrefix = new long[k];
        Arrays.fill(minPrefix, Long.MAX_VALUE / 2);
        long res = Long.MIN_VALUE;
        for (int i = 0; i <= n; i++) {
            int rem = i % k;
            res = Math.max(res, prefix[i] - minPrefix[rem]);
            minPrefix[rem] = Math.min(minPrefix[rem], prefix[i]);
        }
        return res;
    }

}

性能

目标

给你一个二进制数组 nums ，你需要从中删掉一个元素。

请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。

如果不存在这样的子数组，请返回 0 。

示例 1：

输入：nums = [1,1,0,1]
输出：3
解释：删掉位置 2 的数后，[1,1,1] 包含 3 个 1 。

示例 2：

输入：nums = [0,1,1,1,0,1,1,0,1]
输出：5
解释：删掉位置 4 的数字后，[0,1,1,1,1,1,0,1] 的最长全 1 子数组为 [1,1,1,1,1] 。

示例 3：

输入：nums = [1,1,1]
输出：2
解释：你必须要删除一个元素。

说明：

• 1 <= nums.length <= 10^5
• nums[i] 要么是 0 要么是 1 。

思路

有一个二进制数组 nums，从中删除一个元素，求剩余元素中连续的 1 的最大长度。

计算从当前下标为起点的连续 1 的结束下标，end - start 表示连续 1 的长度，允许删掉一个元素可以直接加上 以 end + 1 为起点的连续 1 的个数。

更优的解法是使用滑动窗口计算最长子数组长度，要求窗口内部至多一个 0。

代码

/**
 * @date 2025-08-24 12:20
 */
public class LongestSubarray1493 {

    public int longestSubarray(int[] nums) {
        int n = nums.length;
        int res = 0;
        int i = 0;
        while (i < n) {
            int start = i;
            while (i < n && nums[i] == 1) {
                i++;
            }
            for (int j = start; j < i; j++) {
                nums[j] = i;
            }
            if (i == start) {
                nums[i] = i;
                i++;
            }
        }
        for (int j = 0; j < n; j++) {
            res = Math.max(res, nums[j] - j + (nums[j] < n - 1 ? nums[nums[j] + 1] - nums[j] - 1 : 0));
        }
        return res == n ? n - 1 : res;
    }

}

性能

目标

给你一个整数数组 nums ，返回全部为 0 的 子数组 数目。

子数组 是一个数组中一段连续非空元素组成的序列。

示例 1：

输入：nums = [1,3,0,0,2,0,0,4]
输出：6
解释：
子数组 [0] 出现了 4 次。
子数组 [0,0] 出现了 2 次。
不存在长度大于 2 的全 0 子数组，所以我们返回 6 。

示例 2：

输入：nums = [0,0,0,2,0,0]
输出：9
解释：
子数组 [0] 出现了 5 次。
子数组 [0,0] 出现了 3 次。
子数组 [0,0,0] 出现了 1 次。
不存在长度大于 3 的全 0 子数组，所以我们返回 9 。

示例 3：

输入：nums = [2,10,2019]
输出：0
解释：没有全 0 子数组，所以我们返回 0 。

说明：

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

思路

返回数组的全 0 子数组个数。

长度为 k 的子数组个数为 (1 + k) * k / 2。可以使用贪心策略，如果当前元素是 0 找到以它为起点的最长连续 0 数组，计算子数组个数。

代码

/**
 * @date 2025-08-19 8:54
 */
public class ZeroFilledSubarray2348 {

    public long zeroFilledSubarray(int[] nums) {
        long res = 0L;
        int n = nums.length;
        int i = 0;
        while (i < n){
            if (nums[i] != 0){
                i++;
                continue;
            }
            int start = i;
            while (i < n && nums[i] == 0){
                i++;
            }
            int cnt = i - start;
            res += (1L + cnt) * cnt / 2;
        }

        return res;
    }
}

性能

目标

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

说明：

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

思路

求满足条件的子数组的最大长度，要求子数组最多包含两个不同的元素。

滑动窗口。

代码

/**
 * @date 2025-08-04 8:51
 */
public class TotalFruit904 {

    public int totalFruit(int[] fruits) {
        int n = fruits.length;
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int l = 0;
        for (int i = 0; i < n; i++) {
            map.merge(fruits[i], 1, Integer::sum);
            while (map.size() > 2) {
                map.merge(fruits[l], -1, Integer::sum);
                if (map.get(fruits[l]) == 0) {
                    map.remove(fruits[l]);
                }
                l++;
            }
            res = Math.max(res, i - l + 1);
        }
        return res;
    }

}

性能