LeetCode 3285 找到稳定山的下标

问题描述

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

对于下标不为 0 的一座山，如果它左侧相邻的山的高度 严格大于 threshold ，那么我们称它是 稳定 的。我们定义下标为 0 的山 不是 稳定的。

请你返回一个数组，包含所有 稳定 山的下标，你可以以 任意 顺序返回下标数组。

解题思路

初次邂逅这道题，脑海中或许会迅速浮现出遍历数组的基础解法。没错，遍历就是那把开启解题大门的钥匙。

从数组的第二位（下标 1）起，逐座山细细端详，查看其左侧邻居是否足够高大，也就是高度大于 threshold。一旦觅得满足此条件的山，便迫不及待地将其下标妥善珍藏起来，静待后续整合。

然而，若想更臻完美，还需深思熟虑一种特殊情形。一座山仅左侧达标还不够，倘若后续冒出更高的山峰，那它的 “稳定” 之名便摇摇欲坠。故而，在初步判断左侧条件后，不妨优雅地开启一段内层小循环，继续探索其后继山脉，确保后续无 “后来居上” 者，方能笃定其稳定地位。

代码实现

#include <stdio.h>
#include <stdlib.h>


//辅助函数
int* stableMountains(int* height, int heightSize, int threshold, int* returnSize) {
    int* stableIndices = (int*)malloc(sizeof(int) * heightSize);//动态分配内存
    int count = 0;

    for (int i = 1; i < heightSize; i++) {
        if (height[i - 1] > threshold) {
            stableIndices[count++] = i;
        }
    }

    *returnSize = count;
    if (count == 0) {
        free(stableIndices);
        return NULL;
    }
    return stableIndices;
}

int main(){
    //定义数组
    int height[] = {1,2,3,4,5};
    int heightSize = sizeof(height) / sizeof(height[0]); // 数组大小
    //定义需要满足的要求
    int threshold = 2;
    int returnSize; // 稳定山的数量

    int* stableIndices = stableMountains(height, heightSize, threshold, &returnSize);

    // 打印稳定山的下标
    printf("Stable Mountain indices: ");
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", stableIndices[i]);
    }
    printf("\n");

    // 释放分配的内存
    free(stableIndices);

    return 0;
}

复杂度分析

• 时间复杂度：主要受外层循环和内层循环牵制。外层循环遍历 n - 1 座山，每次内层循环最坏情况要扫视剩余山脉，故而整体时间复杂度为 ，不过平均状况下，内层循环不会全程奔波，复杂度稍显乐观。
• 空间复杂度：因稳定山下标数组在极端时可与原数组等大，所以空间复杂度是 ，额外变量皆为常量级，不影响大局。

优化拓展

优化方向：时间复杂度上，单调栈方案堪称妙策。借助单调递减栈存储山脉高度，遍历之际，入栈出栈行云流水，轻松定位稳定山，瞬间将复杂度降至 O(n)。空间管理方面，若稳定山稀缺，动态扩容机制可大显身手，按需分配内存，避免空间浪费。同时，强化输入参数校验，如杜绝 height 为空、管控 threshold 值域，让程序坚如磐石。