“比左边大且比右边小”的元素指严格大于左侧所有元素、严格小于右侧所有元素的元素；需预处理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 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 left_max[i] && arr[i]
<h3>边界和重复值必须显式处理</h3>
<p>常见错误是忽略首尾元素或相等情况：</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master"><img
src="https://img.php.cn/upload/skill/000/000/081/179051228971575.jpg" alt="C++ Code Review Master" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master" class="overflowclass">C++ Code Review Master</a>
<p class="overflowclass">组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。</p>
</div>
<a rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<ul>
<li>索引 <code>0</code>：左侧无元素，<code>left_max[0]</code> 是 <code>INT_MIN</code>，所以只要 <code>arr[0] 就满足“比左边大”（空集视为恒真），但语义上是否允许？需按题意确认——多数算法题**要求左侧非空且右侧非空**，即只检查 <code>i</code> 从 <code>1</code> 到 <code>n-2</code></code>
</li>
<li>索引 <code>n-1</code>：右侧为空，<code>right_min[n-1]</code> 是 <code>INT_MAX</code>，<code>arr[n-1] 恒成立，但同样应排除</code>
</li>
<li>重复值：题目说“比左边大”“比右边小”，是严格不等，所以 <code>arr[i] == left_max[i]</code> 或 <code>arr[i] == right_min[i]</code> 都不满足</li>
</ul>
<p>因此实际循环应写成 <code>for (int i = 1; i ，并确保 <code>left_max</code> 和 <code>right_min</code> 的定义与之匹配。</code></p>
<h3>用 std::minmax_element 会破坏时间复杂度</h3>
<p>有人试图对每个 <code>i</code> 调用 <code>std::minmax_element</code> 找左右最值，这看起来简洁，但每次调用都是 O(n)，整体退化为 O(n²)。尤其在 <code>n > 10⁴</code> 时可能超时。</p>
<ul>
<li>
<code>std::min_element(arr.begin(), arr.begin()+i)</code> 对每个 <code>i</code> 重算，无缓存</li>
<li>即使手写循环，没做预处理也一样慢</li>
<li>空间换时间在这里非常值得：仅多用 O(n) 空间，换来 O(n) 时间</li>
</ul>
<p>真正容易被忽略的是：当数组有平台（连续相同最大值）或大量重复时，<code>left_max</code> 和 <code>right_min</code> 的递推仍完全有效，无需额外去重逻辑。</p></int></int></int></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
