如何高效解决CSES Mountain Range问题？优化超时解法

这是CSES的Mountain Range问题：

有n座排成一行的山，每座山有特定高度。你从某座山开始滑翔，当山a比山b及a和b之间所有山都高时，可从a滑翔到b。求路线中最多能访问的山的数量。
第一行输入整数n，表示山的数量；第二行输入n个整数h₁,h₂,…,hₙ，表示各山的高度。

约束条件：

1 ≤ n ≤ 2×10^5
1 ≤ hᵢ ≤ 10^9

你采用的修改版Dijkstra思路，本质是在DAG上求最长路径，但每次处理节点时向左右遍历直到遇到更高的山，在最坏情况（比如严格递减的序列）下时间复杂度会达到O(n²)，对于n=2e5的规模来说完全无法通过，这就是超时的核心原因。

优化思路：单调栈+动态规划 #

问题的核心是，每个山的最长滑翔路径可以拆分为从左侧到达该山的最长路径和从该山出发向右侧的最长路径，两者相加再减去重复计算的当前山，就是以该山为最高点的最长路径，最终答案取所有山的这个值的最大值。

我们可以用单调栈在O(n)时间内计算两个DP数组：

• left_dp[i]：以第i座山为终点的最长滑翔路径长度（从左侧山滑翔到i的最长路径）
• right_dp[i]：以第i座山为起点的最长滑翔路径长度（从i滑翔到右侧山的最长路径）

计算left_dp数组（从左到右遍历）

维护一个严格递减的栈，栈中存储(高度, 对应left_dp值)的 pair：

• 对于每个i，弹出栈顶所有高度≤h[i]的元素（这些山无法滑翔到i，因为i的高度不低于它们）
• 若栈为空，说明左侧没有能滑翔到i的山，left_dp[i] = 1
• 否则，栈顶元素是左侧第一个比i高的山，left_dp[i] = 栈顶的left_dp值 + 1
• 将当前山的(h[i], left_dp[i])压入栈

计算right_dp数组（从右到左遍历）

同样维护一个严格递减的栈，栈中存储(高度, 对应right_dp值)的 pair：

• 对于每个i，弹出栈顶所有高度≤h[i]的元素，同时记录这些元素中的最大right_dp值（这些山都是i可以直接或间接到达的）
• 若没有弹出任何元素（栈空或栈顶高度>h[i]），说明i无法滑翔到右侧任何山，right_dp[i] = 1
• 否则，right_dp[i] = 记录的最大right_dp值 + 1
• 将当前山的(h[i], right_dp[i])压入栈

计算最终答案

遍历所有i，计算left_dp[i] + right_dp[i] - 1，取最大值即为答案。

实现代码 #

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    
    vector<int> left_dp(n, 1);
    stack<pair<int, int>> left_stack; // (height, dp_value)
    for (int i = 0; i < n; ++i) {
        while (!left_stack.empty() && left_stack.top().first <= h[i]) {
            left_stack.pop();
        }
        if (!left_stack.empty()) {
            left_dp[i] = left_stack.top().second + 1;
        }
        left_stack.emplace(h[i], left_dp[i]);
    }
    
    vector<int> right_dp(n, 1);
    stack<pair<int, int>> right_stack; // (height, dp_value)
    for (int i = n - 1; i >= 0; --i) {
        int max_right = 0;
        while (!right_stack.empty() && right_stack.top().first <= h[i]) {
            max_right = max(max_right, right_stack.top().second);
            right_stack.pop();
        }
        if (max_right != 0) {
            right_dp[i] = max_right + 1;
        }
        right_stack.emplace(h[i], right_dp[i]);
    }
    
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, left_dp[i] + right_dp[i] - 1);
    }
    cout << ans << '\n';
    
    return 0;
}

代码说明 #

• 使用ios::sync_with_stdio(false); cin.tie(nullptr);加速输入输出，避免因IO慢导致超时
• 两个单调栈分别处理左右方向的DP数组，每个元素仅入栈和出栈一次，保证O(n)时间复杂度
• 最终通过合并左右DP数组的结果，得到全局最长滑翔路径长度

内容的提问来源于stack exchange，提问作者Isabella