牛客4485题解题指南：最短子序列问题的优化解法与代码解析

一、题目解读

牛客4485题要求在一个整数数组中找到最短的子序列长度，该子序列需包含原数组的所有“转折点”（即单调递增或递减的区间边界）。题目关键在于识别转折点并确定最小覆盖范围，需平衡时间与空间效率。

二、解题思路

采用“定位转折点+区间扩展”策略：

1. 从左到右找到首个“下降点”（打破递增趋势的位置），记为start；

2. 从右到左找到首个“上升点”（打破递减趋势的位置），记为end；

3. 计算中间区间的最小/最大值，向两侧扩展直至包含所有极值点；

4. 最终子序列长度为end - start + 1。

核心逻辑：通过转折点定位缩小搜索范围，避免全局遍历。

三、解题步骤

1. 初始化边界：start=0, end=n-1；

2. 定位左转折点：循环右移start直至找到首个下降点（A[start] > A[start+1]）；

3. 定位右转折点：循环左移end直至找到首个上升点（A[end] < A[end-1]）；

4. 计算中间极值：min_val与max_val为[start, end]区间内的最小/最大值；

5. 左扩展：若A[start-1] > min_val，继续左移start；

6. 右扩展：若A[end+1] < max_val，继续右移end；

7. 返回长度：end - start + 1。

通过双向扩展确保包含所有关键元素，减少冗余区间。

四、代码与注释

class ShortSubsequence {  
public:  
    int findShortest(vector<int> A, int n) {  
        int start = 0, end = n - 1; // 初始化边界  
        // 从左往右找第一个下降点  
        while (start < n - 1 && A[start] <= A[start + 1]) start++;  
        if (start == n - 1) return 0; // 若全递增，直接返回0  
        // 从右往左找第一个上升点  
        while (end > 0 && A[end] >= A[end - 1]) end--;  
        // 找出中间段的最小最大值  
        int min_val = *min_element(A.begin() + start, A.begin() + end + 1);  
        int max_val = *max_element(A.begin() + start, A.begin() + end + 1);  
        // 向左扩展  
        while (start > 0 && A[start - 1] > min_val) start--;  
        // 向右扩展  
        while (end < n - 1 && A[end + 1] < max_val) end++;  
        return end - start + 1;  
    }  
};

注释解析：

● 利用min_element与max_element快速定位区间极值，避免手动遍历；

● 边界判断（start=n-1时数组已有序）减少无效计算；

● 双向扩展逻辑确保子序列涵盖所有必要转折点。

五、总结

该解法巧妙利用转折点定位与极值扩展，将时间复杂度优化至O(n)（单次线性扫描+常数级极值查找）。适用于数据规模较大时的高效求解。优化点在于减少冗余搜索，通过数学特性精准锁定目标区间。对算法逻辑与边界处理的把控是解题关键。

参考：牛客4485题解