本文介绍如何在java中高效判断一个整数数组是否构成“山形”（先非降后严格降）或“谷形”（先非升后严格升）结构，即存在唯一转折索引i，使数组在i处达到峰值或谷值，并给出正确、健壮的实现方案。
本文介绍如何在java中高效判断一个整数数组是否构成“山形”（先非降后严格降）或“谷形”（先非升后严格升）结构，即存在唯一转折索引i，使数组在i处达到峰值或谷值，并给出正确、健壮的实现方案。
要解决该问题，核心在于识别数组中是否存在一个转折点索引 i（0 ≤ i ，使得整个数组满足以下两种模式之一：
山形（Peak Pattern）：arr[0] ≤ arr[1] ≤ … ≤ arr[i] > arr[i+1] > … > arr[n−1]
（前半段非递减，后半段严格递减，且 i 是唯一峰值位置，允许 i = n−1，即纯上升序列）谷形（Valley Pattern）：arr[0] ≥ arr[1] ≥ … ≥ arr[i] （前半段非递增，后半段严格递增，且 i 是唯一谷值位置，允许 i = 0 或 i = n−1）
注意：题目示例中 1 2 5 3 1 满足山形（i=2，对应值 5），而 1 2 5 9 是纯上升序列（i=3，即末尾），也合法；但 1 8 5 6 7 2 6 多次起伏，不满足单一转折。
原代码存在多个关键缺陷：
- 嵌套循环逻辑混乱，未明确定义“转折点”，导致条件交叉覆盖；
- 数组越界：for (int k = i; k
- 未区分“非递减”与“严格递减”等语义，且标志位 isConditionMet 被反复覆盖，最终结果不可靠。
✅ 正确解法应采用两次预处理扫描，时间复杂度 O(n)，空间 O(n)，逻辑清晰、无越界风险：
立即学习“Java免费学习笔记（深入）”；
import java.util.Scanner;
public class MountainValleyChecker {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("Enter n: ");
int n = input.nextInt();
if (n == 0) {
System.out.println("No");
return;
}
int[] arr = new int[n];
System.out.println("Enter " + n + " integers:");
for (int i = 0; i < n; i++) {
arr[i] = input.nextInt();
}
// Step 1: Compute leftMax[i] = true if arr[0..i] is non-decreasing
boolean[] leftNonDecreasing = new boolean[n];
leftNonDecreasing[0] = true;
for (int i = 1; i < n; i++) {
leftNonDecreasing[i] = leftNonDecreasing[i-1] && (arr[i-1] <= arr[i]);
}
// Step 2: Compute rightMax[i] = true if arr[i..n-1] is strictly decreasing
boolean[] rightStrictlyDecreasing = new boolean[n];
rightStrictlyDecreasing[n-1] = true;
for (int i = n-2; i >= 0; i--) {
rightStrictlyDecreasing[i] = rightStrictlyDecreasing[i+1] && (arr[i] > arr[i+1]);
}
// Step 3: Check for peak pattern: exists i such that
// leftNonDecreasing[i] && rightStrictlyDecreasing[i]
boolean hasPeak = false;
for (int i = 0; i < n; i++) {
if (leftNonDecreasing[i] && rightStrictlyDecreasing[i]) {
hasPeak = true;
break;
}
}
// Step 4: Compute leftNonIncreasing[i] = true if arr[0..i] is non-increasing
boolean[] leftNonIncreasing = new boolean[n];
leftNonIncreasing[0] = true;
for (int i = 1; i < n; i++) {
leftNonIncreasing[i] = leftNonIncreasing[i-1] && (arr[i-1] >= arr[i]);
}
// Step 5: Compute rightStrictlyIncreasing[i] = true if arr[i..n-1] is strictly increasing
boolean[] rightStrictlyIncreasing = new boolean[n];
rightStrictlyIncreasing[n-1] = true;
for (int i = n-2; i >= 0; i--) {
rightStrictlyIncreasing[i] = rightStrictlyIncreasing[i+1] && (arr[i] < arr[i+1]);
}
// Step 6: Check for valley pattern: exists i such that
// leftNonIncreasing[i] && rightStrictlyIncreasing[i]
boolean hasValley = false;
for (int i = 0; i < n; i++) {
if (leftNonIncreasing[i] && rightStrictlyIncreasing[i]) {
hasValley = true;
break;
}
}
System.out.println(hasPeak || hasValley ? "Yes" : "No");
}
}? 关键注意事项：
- 边界安全：所有循环均使用 i = 0，避免越界；rightStrictlyDecreasing[i] 依赖 i+1，故从 n−2 倒序遍历。
- 语义精确：山形要求后半段“严格递减”（>），而非“≥”，否则 1,2,2,1 会被误判（实际符合，但若允许多个相等峰顶需按题意调整）；同理谷形后半段用
- 效率优化：两次正向+两次反向扫描，O(n) 时间，优于暴力 O(n³)；可进一步压缩为 O(1) 空间（仅维护前缀状态变量），但当前写法更易理解与调试。
- 特例处理：n == 1 时，单元素既满足山形（leftNonDecreasing[0] && rightStrictlyDecreasing[0] 为 true && true）也满足谷形，输出 "Yes"，符合题目隐含逻辑。
? 总结：判断单峰/单谷结构的关键是分离“左侧单调性”与“右侧单调性”，通过预计算布尔数组消除嵌套循环和越界风险。该模式可扩展至寻找所有合法转折点、或支持自定义单调阈值（如允许最多1次波动），是数组单调性分析的经典范式。
