标签： 数组

目标

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

性能

目标

给你一个正整数 n，表示一个 n x n 的城市，同时给定一个二维数组 buildings，其中 buildings[i] = [x, y] 表示位于坐标 [x, y] 的一个 唯一 建筑。

如果一个建筑在四个方向（左、右、上、下）中每个方向上都至少存在一个建筑，则称该建筑 被覆盖 。

返回 被覆盖 的建筑数量。

示例 1：

输入: n = 3, buildings = [[1,2],[2,2],[3,2],[2,1],[2,3]]
输出: 1
解释:
只有建筑 [2,2] 被覆盖，因为它在每个方向上都至少存在一个建筑：
上方 ([1,2])
下方 ([3,2])
左方 ([2,1])
右方 ([2,3])
因此，被覆盖的建筑数量是 1。

示例 2：

输入: n = 3, buildings = [[1,1],[1,2],[2,1],[2,2]]
输出: 0
解释:
没有任何一个建筑在每个方向上都有至少一个建筑。

示例 3：

输入: n = 5, buildings = [[1,3],[3,2],[3,3],[3,5],[5,3]]
输出: 1
解释:
只有建筑 [3,3] 被覆盖，因为它在每个方向上至少存在一个建筑：
上方 ([1,3])
下方 ([5,3])
左方 ([3,2])
右方 ([3,5])
因此，被覆盖的建筑数量是 1。

说明：

• 2 <= n <= 10^5
• 1 <= buildings.length <= 10^5
• buildings[i] = [x, y]
• 1 <= x, y <= n
• buildings 中所有坐标均 唯一 。

思路

二维数组 buildings 表示建筑的坐标，如果建筑的上下左右均存在其它建筑，则称该建筑被包围。统计被包围建筑的个数。

只需记录每一行每一列的最大值与最小值，判断当前建筑是否在其中。

代码

/**
 * @date 2025-12-11 14:03
 */
public class CountCoveredBuildings3531 {

    public int countCoveredBuildings_v1(int n, int[][] buildings) {
        int[] minX = new int[n + 1];
        int[] maxX = new int[n + 1];
        int[] minY = new int[n + 1];
        int[] maxY = new int[n + 1];
        Arrays.fill(minX, n + 1);
        Arrays.fill(minY, n + 1);
        for (int[] building : buildings) {
            int x = building[0];
            int y = building[1];
            minX[y] = Math.min(minX[y], x);
            maxX[y] = Math.max(maxX[y], x);
            minY[x] = Math.min(minY[x], y);
            maxY[x] = Math.max(maxY[x], y);
        }
        int res = 0;
        for (int[] building : buildings) {
            int x = building[0];
            int y = building[1];
            if (x > minX[y] && x < maxX[y] && y > minY[x] && y < maxY[x]) {
                res++;
            }
        }
        return res;
    }

}

性能

目标

给你一个整数数组 nums。

特殊三元组 定义为满足以下条件的下标三元组 (i, j, k)：

• 0 <= i < j < k < n，其中 n = nums.length
• nums[i] == nums[j] * 2
• nums[k] == nums[j] * 2

返回数组中 特殊三元组 的总数。

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

示例 1：

输入： nums = [6,3,6]
输出： 1
解释：
唯一的特殊三元组是 (i, j, k) = (0, 1, 2)，其中：
nums[0] = 6, nums[1] = 3, nums[2] = 6
nums[0] = nums[1] * 2 = 3 * 2 = 6
nums[2] = nums[1] * 2 = 3 * 2 = 6

示例 2：

输入： nums = [0,1,0,0]
输出： 1
解释：
唯一的特殊三元组是 (i, j, k) = (0, 2, 3)，其中：
nums[0] = 0, nums[2] = 0, nums[3] = 0
nums[0] = nums[2] * 2 = 0 * 2 = 0
nums[3] = nums[2] * 2 = 0 * 2 = 0

示例 3：

输入： nums = [8,4,2,8,4]
输出： 2
解释：
共有两个特殊三元组：
(i, j, k) = (0, 1, 3)
nums[0] = 8, nums[1] = 4, nums[3] = 8
nums[0] = nums[1] * 2 = 4 * 2 = 8
nums[3] = nums[1] * 2 = 4 * 2 = 8
(i, j, k) = (1, 2, 4)
nums[1] = 4, nums[2] = 2, nums[4] = 4
nums[1] = nums[2] * 2 = 2 * 2 = 4
nums[4] = nums[2] * 2 = 2 * 2 = 4

说明：

• 3 <= n == nums.length <= 10^5
• 0 <= nums[i] <= 10^5

思路

找到数组 nums 的三元组 (i, j, k) 满足 nums[i] == nums[k] == 2 * nums[j]，返回特殊三元组的个数。注意这里三元组是元素下标所以不会重复。

枚举右端点，如果为偶数，查找中间元素 nums[k]/2 作为右端点的二元组个数，该二元组 (i, j) 可以同时维护，找到左侧 i 的个数，满足 nums[i] == 2 * nums[j]。

代码

/**
 * @date 2025-12-09 8:55
 */
public class SpecialTriplets3583 {

    public int specialTriplets_v1(int[] nums) {
        int n = nums.length;
        int mod = 1000000007;
        Map<Integer, Long> cnt = new HashMap<>();
        Map<Integer, Long> binaryCnt = new HashMap<>();
        long res = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] % 2 == 0) {
                res += binaryCnt.getOrDefault(nums[i] / 2, 0L);
            }
            binaryCnt.merge(nums[i], cnt.getOrDefault(nums[i] * 2, 0L), Long::sum);
            cnt.merge(nums[i], 1L, Long::sum);
        }
        return (int) (res % 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;
    }

}

性能

目标

给你一个二维 二进制 数组 grid。请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形，并且满足 grid 中所有的 1 都在矩形的内部。

返回这个矩形可能的 最小 面积。

示例 1：

输入： grid = [[0,1,0],[1,0,1]]
输出： 6
解释：
这个最小矩形的高度为 2，宽度为 3，因此面积为 2 * 3 = 6。

示例 2：

输入： grid = [[0,0],[1,0]]
输出： 1
解释：
这个最小矩形的高度和宽度都是 1，因此面积为 1 * 1 = 1。

说明：

• 1 <= grid.length, grid[i].length <= 1000
• grid[i][j] 是 0 或 1。
• 输入保证 grid 中至少有一个 1 。

思路

已知一个二维 二进制数组，找出包含矩阵中所有 1 的矩阵的最小面积。

找到 1 的横纵坐标的上下界即可。

代码

/**
 * @date 2025-08-22 10:08
 */
public class MinimumArea3195 {

    public int minimumArea(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int rowMin = m - 1, rowMax = 0;
        int colMin = n - 1, colMax = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    rowMin = Math.min(rowMin, i);
                    rowMax = Math.max(rowMax, i);
                    colMin = Math.min(colMin, j);
                    colMax = Math.max(colMax, j);
                }
            }
        }
        return (rowMax - rowMin + 1) * (colMax - colMin + 1);
    }

}

性能

目标

一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。

给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。

示例 1：

输入：changed = [1,3,4,2,6,8]
输出：[1,3,4]
解释：一个可能的 original 数组为 [1,3,4] :
- 将 1 乘以 2 ，得到 1 * 2 = 2 。
- 将 3 乘以 2 ，得到 3 * 2 = 6 。
- 将 4 乘以 2 ，得到 4 * 2 = 8 。
其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。

示例 2：

输入：changed = [6,3,0,1]
输出：[]
解释：changed 不是一个双倍数组。

示例 3：

输入：changed = [1]
输出：[]
解释：changed 不是一个双倍数组。

说明：

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

思路

所谓双倍数组指的是由原数组以及其每个元素乘以2之后的元素合并在一起的数组。现在想要从双倍数组还原为原数组，如果不是合法的双倍数组则返回空数组。

首先，如果元素个数为奇数肯定不是双倍数组。注意到数组中的元素如果是奇数那么一定属于原数组。由于返回数组的顺序任意，那么先排序会更好处理。

接着就想到将奇数与偶数分开，然后看奇数*2是否有相应的偶数对应，或者可以将偶数元素/2看是否有奇数对应（不过这样就得处理0的情况，因为0只能与它自己匹配）。匹配完成后可能还剩下原数组中的偶数元素与其对应的双倍元素。

该如何处理呢？看了具体的例子很容易有一些想当然的想法，比如剩余[2,2,4,4]很容易将其平分为两部分，然后同时比较这两部分相应的位置是否满足二倍关系。这种假设是没有根据的，也是不对的，比如剩余[2、2、4、4、4、6、8、12]也是合法的。那我们该怎么比较呢？

这时突然有一个想法出现在大脑中，可以先将当前元素存到队列中，如果后面的元素不是其二倍就添加到队列中，如果是则将队列的第一个元素取出，这样遍历完之后看队列中是否还有数据即可。我们之所以可以这么做是因为前面排过序了，队首元素的二倍元素一定会最先出现。如果不排序的话，比如说[2,1]，2先加入队列，后加入的1就无法匹配了。再比如[4,8,2,16]，4与8匹配了，剩下的就匹配不了了。

有了这个想法之后，前面区分奇数、偶数，对0做特殊处理就都没有必要了。

网友还介绍了一种消消乐的方法，可以不排序。这个需要先统计各元素出现的次数，然后如果x % 2 == 0 && cnt.containsKey(x / 2)则跳过，即如果 x/2 在 cnt 中，则跳过，直到找到开始的那个x，然后一次性处理之前被跳过的2x、4x、6x...。这里其实也利用了顺序，只不过没有排序而是先找到不能再分的那个初始节点再向后倍增。

还有的使用大数组保存了 0~max 元素出现次数的数组cnt，然后遍历cnt，如果cnt[i]>0 而 2*i>max || cnt[2i]==0 直接返回空数组，否则cnt[2i]--。这个方法也不用排序，是因为统计个数时变相地将数组元素映射为下标，遍历cnt数组是从小到大有序的。

代码

/**
 * @date 2024-04-18 8:48
 */
public class FindOriginalArray2007 {

    public int[] findOriginalArray(int[] changed) {
        int n = changed.length;
        if (n % 2 == 1) {
            return new int[0];
        }
        Arrays.sort(changed);
        int originLength = n / 2;
        int[] res = new int[originLength];
        Deque<Integer> collect = new ArrayDeque<>();
        int i = 0;
        for (int j = 0; j < changed.length; j++) {
            if (collect.size() == 0 || changed[j] % 2 == 1 || !collect.peek().equals(changed[j] / 2)) {
                collect.add(changed[j]);
            } else {
                res[i++] = collect.poll();
            }
        }
        if (collect.size() > 0) {
            return new int[0];
        }
        return res;
    }

}

性能

目标

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

说明：

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

思路

最简单的想法是先计算所有元素的乘积，然后挨个除，但是题目要求不能用除法，略过。

后面又要求不要创建额外的空间，即最好只创建一个用于返回结果的数组。

考虑先保存数组元素的右/左侧的乘积，然后二次遍历计算左/右侧乘积，然后与之前保存的值相乘即可。

网友还有一种一次遍历的写法，初始化结果数组为1，同时从前计算左边乘积，从后计算右边乘积，但是每次循环执行了4次乘法，效率并不高。

代码

/**
 * @date 2024-04-07 11:35
 */
public class ProductExceptSelf238 {

    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] right = new int[n];
        right[n- 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            right[i] = nums[i + 1] * right[i + 1];
        }
        int left = 1;
        for (int i = 1; i < n; i++) {
            left *= nums[i - 1];
            right[i] *= left;
        }
        return right;
    }

    /**  一次遍历的版本 */
    public int[] productExceptSelf_v1(int[] nums) {
        int[] res = new int[nums.length];
        Arrays.fill(res, 1);
        int j = nums.length - 2;
        int left = 1, right = 1;
        for (int i = 1; i < nums.length; i++) {
            left *= nums[i - 1];
            right *= nums[j + 1];
            res[i] = left * res[i];
            res[j] = right * res[j];
            j--;
        }
        return res;
    }
}

性能