Easy

题目描述

有 n 座山脉排成一行，每座山都有一个高度。给你一个整数数组 height，其中 height[i] 表示第 i 座山的高度，以及一个整数 threshold。

如果一座山前面的山（如果存在）的高度严格大于 threshold，则该山被称为稳定的。注意第 0 座山不稳定。

返回一个包含所有稳定山脉索引的数组，顺序任意。

示例 1：

输入：height = [1,2,3,4,5], threshold = 2
输出：[3,4]
解释：
- 第 3 座山稳定，因为 height[2] == 3 大于 threshold == 2
- 第 4 座山稳定，因为 height[3] == 4 大于 threshold == 2

示例 2：

输入：height = [10,1,10,1,10], threshold = 3
输出：[1,3]

示例 3：

输入：height = [10,1,10,1,10], threshold = 10
输出：[]

提示：

  • 2 <= n == height.length <= 100
  • 1 <= height[i] <= 100
  • 1 <= threshold <= 100

解题思路

这是一道简单的数组遍历题目。我们需要找到所有稳定的山脉，即前一座山的高度严格大于阈值的山脉。

解题思路：

由于第 0 座山没有前一座山，所以它不可能稳定。我们只需要从索引 1 开始遍历数组，对于每个索引 i，检查 height[i-1] 是否严格大于 threshold。如果满足条件，就将索引 i 加入结果数组。

算法步骤：

  1. 初始化一个空的结果数组
  2. 从索引 1 开始遍历到数组末尾
  3. 对于每个索引 i，检查 height[i-1] > threshold
  4. 如果条件成立，将索引 i 添加到结果数组中
  5. 返回结果数组

这是一个直接的线性扫描问题，时间复杂度为 O(n)，空间复杂度为 O(1)（不考虑输出数组的空间）。

代码实现

class Solution {
public:
    vector<int> stableMountains(vector<int>& height, int threshold) {
        vector<int> result;
        for (int i = 1; i < height.size(); i++) {
            if (height[i - 1] > threshold) {
                result.push_back(i);
            }
        }
        return result;
    }
};

class Solution:
    def stableMountains(self, height: List[int], threshold: int) -> List[int]:
        result = []
        for i in range(1, len(height)):
            if height[i - 1] > threshold:
                result.append(i)
        return result

public class Solution {
    public IList<int> StableMountains(int[] height, int threshold) {
        IList<int> result = new List<int>();
        for (int i = 1; i < height.Length; i++) {
            if (height[i - 1] > threshold) {
                result.Add(i);
            }
        }
        return result;
    }
}

var stableMountains = function(height, threshold) {
    const result = [];
    for (let i = 1; i < height.length; i++) {
        if (height[i - 1] > threshold) {
            result.push(i);
        }
    }
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组一次，其中 n 是山脉的数量
空间复杂度O(1)只使用常量额外空间，不考虑输出数组

相关题目