✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线100+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

百度-算法岗

题目一：花园路径优化问题

1️⃣：使用栈维护必须保留的观景点，基于三角不等式判断

2️⃣：贪心策略，检查中间点是否为"转折点"

3️⃣：时间复杂度 O(n)，空间复杂度 O(n)

难度：中等

这道题目的关键在于理解三角不等式的应用。对于三个连续的观景点，只有当中间点不是"转折点"时才能被移除。通过维护一个栈来动态判断哪些点可以被安全移除，实现了高效的贪心解法。

题目二：艺术品价值评估问题

1️⃣：分别计算前缀、后缀和中间区间的最大和

2️⃣：使用 Kadane 算法求解最大子数组和

3️⃣：比较三种情况的最大值与总和的关系

难度：中等

这道题目结合了前缀和、后缀和以及经典的最大子数组和问题。通过将问题分解为三种不同的区间类型，避免了复杂的枚举，实现了 O(n) 时间复杂度的高效解法。关键在于理解问题的数学本质和合理的分类讨论。

01. 花园路径优化问题

问题描述

小兰正在设计一个美丽的花园，花园中有一条蜿蜒的小径。这条小径由 个观景点组成，按顺序编号为 ，每个观景点都有一个海拔高度 。

为了让游客在漫步时有更好的体验，小兰定义了小径的"舒适度"：相邻两个观景点之间的高度差的绝对值之和，即 。当小径只有一个观景点时，舒适度为 。

现在小兰想要移除一些观景点（但不能全部移除），使得剩余观景点构成的小径舒适度保持不变。她想知道最多能移除多少个观景点。

输入格式

第一行包含一个正整数 ，表示观景点的数量。

第二行包含 个正整数 ，表示各观景点的海拔高度。

输出格式

输出一行，包含一个整数，表示最多可以移除的观景点数量。

样例输入

10
1 2 8 8 9 1 1 1 5 5

6
6 6 6 6 6 6

样例输出

6

4

数据范围

样例	解释说明
样例1	原始舒适度为 。保留观景点 后舒适度仍为 ，最多可移除 个观景点。
样例2	所有观景点海拔相同，舒适度为 。只需保留首尾两个观景点即可，最多可移除 个观景点。

题解

这道题的关键在于理解什么情况下移除一个观景点不会改变小径的舒适度。

对于三个连续的观景点 ，原来的贡献是 ，如果移除中间的点 ，新的贡献变为 。

根据三角不等式，当且仅当 位于 和 之间时（即 不是"转折点"），等式 才成立。换句话说，如果 ，那么 可以被安全移除。

基于这个观察，我们可以用贪心的思想：从左到右扫描所有观景点，维护一个必须保留的观景点序列。对于每个新的观景点，检查之前序列中的点是否可以被移除。

具体算法：

1. 使用一个栈来维护当前必须保留的观景点
2. 对每个观景点，检查栈顶的点是否可以移除
3. 如果栈中有至少两个点，且倒数第二个点、栈顶点、当前点满足移除条件，就移除栈顶点
4. 将当前点加入栈
5. 最终答案是 减去栈的大小

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

def solve():
    n = int(input())
    h = list(map(int, input().split()))
    
    # 用栈维护必须保留的观景点
    stk = []
    
    for height in h:
        # 检查栈顶元素是否可以移除
        while len(stk) >= 2:
            w = stk[-2]  # 倒数第二个点
            y = stk[-1]  # 栈顶点
            z = height   # 当前点
            
            # 判断 y 是否可以移除：(w-y)*(z-y) >= 0
            if (w - y) * (z - y) >= 0:
                stk.pop()  # 移除栈顶
            else:
                break
        
        stk.append(height)
    
    # 最多可移除的点数
    print(n - len(stk))

if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<long long> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    
    // 用栈维护必须保留的观景点
    vector<long long> stk;
    stk.reserve(n);
    
    for (long long height : h) {
        // 检查栈顶元素是否可以移除
        while (stk.size() >= 2) {
            long long w = stk[stk.size() - 2];  // 倒数第二个点
            long long y = stk.back();           // 栈顶点
            long long z = height;               // 当前点
            
            // 判断 y 是否可以移除：(w-y)*(z-y) >= 0
            if ((w - y) * (z - y) >= 0) {
                stk.pop_back();  // 移除栈顶
            } else {
                break;
            }
        }
        
        stk.push_back(height);
    }
    
    // 最多可移除的点数
    cout << n - (int)stk.size() << '\n';
    
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        long[] h = new long[n];
        for (int i = 0; i < n; i++) {
            h[i] = Long.parseLong(input[i]);
        }
        
        // 用栈维护必须保留的观景点
        List<Long> stk = new ArrayList<>();
        
        for (long height : h) {
            // 检查栈顶元素是否可以移除
            while (stk.size() >= 2) {
                long w = stk.get(stk.size() - 2);  // 倒数第二个点