标签： 数组

目标

有一个大型的 (m - 1) x (n - 1) 矩形田地，其两个对角分别是 (1, 1) 和 (m, n) ，田地内部有一些水平栅栏和垂直栅栏，分别由数组 hFences 和 vFences 给出。

水平栅栏为坐标 (hFences[i], 1) 到 (hFences[i], n)，垂直栅栏为坐标 (1, vFences[i]) 到 (m, vFences[i]) 。

返回通过 移除 一些栅栏（可能不移除）所能形成的最大面积的 正方形 田地的面积，或者如果无法形成正方形田地则返回 -1。

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

注意：田地外围两个水平栅栏（坐标 (1, 1) 到 (1, n) 和坐标 (m, 1) 到 (m, n) ）以及两个垂直栅栏（坐标 (1, 1) 到 (m, 1) 和坐标 (1, n) 到 (m, n) ）所包围。这些栅栏 不能 被移除。

示例 1：

输入：m = 4, n = 3, hFences = [2,3], vFences = [2]
输出：4
解释：移除位于 2 的水平栅栏和位于 2 的垂直栅栏将得到一个面积为 4 的正方形田地。

示例 2：

输入：m = 6, n = 7, hFences = [2], vFences = [4]
输出：-1
解释：可以证明无法通过移除栅栏形成正方形田地。

说明：

• 3 <= m, n <= 10^9
• 1 <= hFences.length, vFences.length <= 600
• 1 < hFences[i] < m
• 1 < vFences[i] < n
• hFences 和 vFences 中的元素是唯一的。

思路

有一个 (m - 1) x (n - 1) 矩形田地，左上角坐标为 (1, 1)，右下角坐标为 (m, n)，田地内部有一些栅栏，水平栅栏 i 的纵坐标为 hFences[i]，垂直栅栏 j 的横坐标为 vFences[j]。可以移除一些栅栏，求能够形成的最大正方形的面积。

使用哈希表分别记录水平与垂直方向可能的间隔，找到最大相等间隔，相乘即可。

代码

/**
 * @date 2026-01-16 8:49
 */
public class MaximizeSquareArea2975 {

    public int maximizeSquareArea(int m, int n, int[] hFences, int[] vFences) {
        Set<Integer> hq = getInterval(m, hFences);
        Set<Integer> vq = getInterval(n, vFences);
        hq.retainAll(vq);
        if (hq.size() == 0) {
            return -1;
        }
        long res = 0;
        int mod = 1000000007;
        for (Integer num : hq) {
            res = Math.max(res, num);
        }
        return (int) (res * res % mod);
    }

    private Set<Integer> getInterval(int edge, int[] fences) {
        Arrays.sort(fences);
        Set<Integer> set = new HashSet<>();
        int n = fences.length;
        for (int i = 0; i < n; i++) {
            set.add(fences[i] - 1);
            set.add(edge - fences[i]);
            for (int j = i + 1; j < n; j++) {
                set.add(fences[j] - fences[i]);
            }
        }
        set.add(edge - 1);
        return set;
    }

}

性能

目标

给你一个长度为 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;
    }
}

性能

目标

给定由 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 ，表示一支股票的历史每日股价，其中 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);
    }

}

性能