Easy

题目描述

给定一个整数数组 nums 和一个整数 k，如果元素 nums[i] 严格大于索引 i - k 和 i + k 处的元素（如果这些索引存在），则认为该元素是好的。如果这两个索引都不存在，nums[i] 仍然被认为是好的。

返回数组中所有好元素的和。

示例 1：

输入：nums = [1,3,2,1,5,4], k = 2
输出：12
解释：
好数字是 nums[1] = 3，nums[4] = 5 和 nums[5] = 4，因为它们严格大于索引 i - k 和 i + k 处的数字。

示例 2：

输入：nums = [2,1], k = 1
输出：2
解释：
唯一的好数字是 nums[0] = 2，因为它严格大于 nums[1]。

约束条件：

  • 2 <= nums.length <= 100
  • 1 <= nums[i] <= 1000
  • 1 <= k <= floor(nums.length / 2)

解题思路

这道题的核心思想是遍历数组中的每个元素，检查它是否满足"好数字"的条件。

解题思路：

  1. 理解好数字的定义：对于位置 i 的元素 nums[i]，如果它严格大于 nums[i-k] 和 nums[i+k]（当这些索引存在时），或者这些索引不存在，则该元素是好数字。

  2. 边界处理：

    • 当 i - k < 0 时，左边界不存在
    • 当 i + k >= n 时，右边界不存在
    • 当两个边界都不存在时，该元素自动成为好数字

  3. 具体判断逻辑：

    • 如果左右边界都存在：nums[i] > nums[i-k] && nums[i] > nums[i+k]
    • 如果只有左边界存在：nums[i] > nums[i-k]
    • 如果只有右边界存在：nums[i] > nums[i+k]
    • 如果两个边界都不存在：直接认为是好数字

  4. 算法流程：遍历每个位置，根据上述逻辑判断是否为好数字，如果是则累加到结果中。

时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

代码实现

class Solution {
public:
    int sumOfGoodNumbers(vector<int>& nums, int k) {
        int n = nums.size();
        int sum = 0;
        
        for (int i = 0; i < n; i++) {
            bool leftExists = (i - k >= 0);
            bool rightExists = (i + k < n);
            
            bool isGood = true;
            
            if (leftExists && nums[i] <= nums[i - k]) {
                isGood = false;
            }
            
            if (rightExists && nums[i] <= nums[i + k]) {
                isGood = false;
            }
            
            if (isGood) {
                sum += nums[i];
            }
        }
        
        return sum;
    }
};

class Solution:
    def sumOfGoodNumbers(self, nums: List[int], k: int) -> int:
        n = len(nums)
        total = 0
        
        for i in range(n):
            left_exists = i - k >= 0
            right_exists = i + k < n
            
            is_good = True
            
            if left_exists and nums[i] <= nums[i - k]:
                is_good = False
            
            if right_exists and nums[i] <= nums[i + k]:
                is_good = False
            
            if is_good:
                total += nums[i]
        
        return total

public class Solution {
    public int SumOfGoodNumbers(int[] nums, int k) {
        int n = nums.Length;
        int sum = 0;
        
        for (int i = 0; i < n; i++) {
            bool leftExists = (i - k >= 0);
            bool rightExists = (i + k < n);
            
            bool isGood = true;
            
            if (leftExists && nums[i] <= nums[i - k]) {
                isGood = false;
            }
            
            if (rightExists && nums[i] <= nums[i + k]) {
                isGood = false;
            }
            
            if (isGood) {
                sum += nums[i];
            }
        }
        
        return sum;
    }
}

var sumOfGoodNumbers = function(nums, k) {
    const n = nums.length;
    let sum = 0;
    
    for (let i = 0; i < n; i++) {
        const leftExists = (i - k >= 0);
        const rightExists = (i + k < n);
        
        let isGood = true;
        
        if (leftExists && nums[i] <= nums[i - k]) {
            isGood = false;
        }
        
        if (rightExists && nums[i] <= nums[i + k]) {
            isGood = false;
        }
        
        if (isGood) {
            sum += nums[i];
        }
    }
    
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 需要遍历数组中的每个元素一次
空间复杂度O(1) - 只使用了常数个额外变量