“比左边大且比右边小”的元素指严格大于左侧所有元素、严格小于右侧所有元素的元素；需预处理left_max和right_min数组，仅检查1≤i≤n-2索引，避免O(n²)暴力解。
什么是“比左边大且比右边小”的元素
这种元素在数组中处于局部极小位置：它严格大于左侧所有元素，又严格小于右侧所有元素。注意不是“比左邻大、比右邻小”，而是**比整个左侧子数组的最大值大，且比整个右侧子数组的最小值小**。例如数组 [5, 1, 3, 2, 4] 中，3 左侧最大是 5，不满足；2 左侧最大是 5，也不满足；只有 4 左侧最大是 5？不对——再看：1 左侧只有 5，1 ，不满足；其实这个数组没有符合条件的元素。而 <code>[3, 1, 4, 2, 5] 中，4 左侧最大是 3，右侧最小是 2，但 4 > 2，不满足；2 左侧最大是 4，2 ，也不行；<code>5 右侧为空，按定义通常不参与比较（右侧无元素时无法满足“比右边小”）。所以必须明确边界处理逻辑。
用两次预处理数组实现 O(n) 时间查找
暴力对每个位置遍历左右两侧是 O(n²)，实际项目中不可取。正确做法是提前算出两个辅助数组：
-
left_max[i]表示arr[0..i-1]中的最大值（i==0时设为 INT_MIN） -
right_min[i]表示arr[i+1..n-1]中的最小值（i==n-1时设为 INT_MAX）
这样对每个 i，只需判断 arr[i] > left_max[i] && arr[i] 即可。
vector<int> findLocalMinima(const vector<int>& arr) {
int n = arr.size();
if (n == 0) return {};
vector<int> left_max(n, INT_MIN);
for (int i = 1; i < n; ++i) {
left_max[i] = max(left_max[i-1], arr[i-1]);
}
vector<int> right_min(n, INT_MAX);
for (int i = n-2; i >= 0; --i) {
right_min[i] = min(right_min[i+1], arr[i+1]);
}
vector<int> res;
for (int i = 0; i < n; ++i) {
if (arr[i] > left_max[i] && arr[i] < right_min[i]) {
res.push_back(arr[i]);
}
}
return res;
}
边界和重复值必须显式处理
常见错误是忽略首尾元素或相等情况：
立即学习“C++免费学习笔记（深入）”；
- 索引
0：左侧无元素，left_max[0]是INT_MIN，所以只要arr[0] < right_min[0]就满足“比左边大”（空集视为恒真），但语义上是否允许？需按题意确认——多数算法题**要求左侧非空且右侧非空**，即只检查i从1到n-2 - 索引
n-1：右侧为空，right_min[n-1]是INT_MAX，arr[n-1] < INT_MAX恒成立，但同样应排除 - 重复值：题目说“比左边大”“比右边小”，是严格不等，所以
arr[i] == left_max[i]或arr[i] == right_min[i]都不满足
因此实际循环应写成 for (int i = 1; i < n-1; ++i)，并确保 left_max 和 right_min 的定义与之匹配。
用 std::minmax_element 会破坏时间复杂度
有人试图对每个 i 调用 std::minmax_element 找左右最值，这看起来简洁，但每次调用都是 O(n)，整体退化为 O(n²)。尤其在 n > 10⁴ 时可能超时。
-
std::min_element(arr.begin(), arr.begin()+i)对每个i重算，无缓存 - 即使手写循环，没做预处理也一样慢
- 空间换时间在这里非常值得：仅多用 O(n) 空间，换来 O(n) 时间
真正容易被忽略的是：当数组有平台（连续相同最大值）或大量重复时，left_max 和 right_min 的递推仍完全有效，无需额外去重逻辑。
