3452. 好数字之和

English Version

题目描述

给定一个整数数组 nums 和一个整数 k，如果元素 nums[i] 严格 大于下标 i - k 和 i + k 处的元素（如果这些元素存在），则该元素 nums[i] 被认为是 好 的。如果这两个下标至少一个不存在，那么 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)

解法

方法一：遍历

我们可以遍历数组 $\textit{nums}$，对于每个元素 $\textit{nums}[i]$，检查是否满足条件：

• 如果 $i \ge k$ 且 $\textit{nums}[i] \le \textit{nums}[i - k]$，则 $\textit{nums}[i]$ 不是好数字；

• 如果 $i + k < \textit{len}(\textit{nums})$ 且 $\textit{nums}[i] \le \textit{nums}[i + k]$，则 $\textit{nums}[i]$ 不是好数字。

• 否则，$\textit{nums}[i]$ 是好数字，我们将其累加到答案中。

遍历结束后，返回答案即可。

时间复杂度 $O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$。

Python3

class Solution:
    def sumOfGoodNumbers(self, nums: List[int], k: int) -> int:
        ans = 0
        for i, x in enumerate(nums):
            if i >= k and x <= nums[i - k]:
                continue
            if i + k < len(nums) and x <= nums[i + k]:
                continue
            ans += x
        return ans

Java

class Solution {
    public int sumOfGoodNumbers(int[] nums, int k) {
        int ans = 0;
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (i >= k && nums[i] <= nums[i - k]) {
                continue;
            }
            if (i + k < n && nums[i] <= nums[i + k]) {
                continue;
            }
            ans += nums[i];
        }
        return ans;
    }
}

C++

class Solution {
public:
    int sumOfGoodNumbers(vector<int>& nums, int k) {
        int ans = 0;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (i >= k && nums[i] <= nums[i - k]) {
                continue;
            }
            if (i + k < n && nums[i] <= nums[i + k]) {
                continue;
            }
            ans += nums[i];
        }
        return ans;
    }
};

Go

func sumOfGoodNumbers(nums []int, k int) (ans int) {
	for i, x := range nums {
		if i >= k && x <= nums[i-k] {
			continue
		}
		if i+k < len(nums) && x <= nums[i+k] {
			continue
		}
		ans += x
	}
	return
}

TypeScript

function sumOfGoodNumbers(nums: number[], k: number): number {
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        if (i >= k && nums[i] <= nums[i - k]) {
            continue;
        }
        if (i + k < n && nums[i] <= nums[i + k]) {
            continue;
        }
        ans += nums[i];
    }
    return ans;
}