企业官网建设流程全解析

这道题的核心思路是 KMP 字符串匹配。

思路

1. 预处理：将 `nums` 数组中相邻元素的差值符号提取出来，得到一个长度为 `n-1` 的新数组 `diff`：
- `nums[i+1] > nums[i]` → `diff[i] = 1`
- `nums[i+1] == nums[i]` → `diff[i] = 0`
- `nums[i+1] < nums[i]` → `diff[i] = -1`

2. KMP 匹配：问题转化为在 `diff` 数组中，有多少个子数组等于 `pattern`。由于 `n` 最大为 10^6，必须使用 KMP 算法在 O(n+m) 时间内完成。

Java 实现

```java
class Solution {
public int countMatchingSubarrays(int[] nums, int[] pattern) {
// 1. 预处理 nums，得到相邻元素的符号数组
int[] diff = new int[nums.length - 1];
for (int i = 1; i < nums.length; i++) {
diff[i - 1] = getSign(nums[i - 1], nums[i]);
}

// 2. 使用 KMP 算法统计 pattern 在 diff 中出现的次数
return kmp(diff, pattern);
}

// 计算两个数的符号关系：1 表示 a < b，-1 表示 a > b，0 表示相等
private int getSign(int a, int b) {
if (a < b) return 1;
if (a > b) return -1;
return 0;
}

// KMP 算法，返回 pattern 在 text 中的出现次数
private int kmp(int[] text, int[] pattern) {
int[] lps = buildLPS(pattern);
int count = 0;
int i = 0; // text 的指针
int j = 0; // pattern 的指针

while (i < text.length) {
if (text[i] == pattern[j]) {
i++;
j++;
if (j == pattern.length) {
count++; // 找到一个匹配
j = lps[j - 1]; // 继续匹配下一个（允许重叠）
}
} else if (j > 0) {
j = lps[j - 1]; // 回退到最长公共前缀
} else {
i++; // pattern[0] 都不匹配，text 指针前进
}
}
return count;
}

// 构建 pattern 的最长公共前后缀数组 (LPS)
private int[] buildLPS(int[] pattern) {
int[] lps = new int[pattern.length];
// lps[0] 默认为 0

for (int i = 1, j = 0; i < pattern.length; i++) {
while (j > 0 && pattern[i] != pattern[j]) {
j = lps[j - 1];
}
if (pattern[i] == pattern[j]) {
lps[i] = ++j;
}
}
return lps;
}
}
```

复杂度分析

- 时间复杂度：O(n + m)。预处理 O(n)，KMP 匹配 O(n + m)。
- 空间复杂度：O(m)。仅需存储 LPS 数组（`diff` 数组可原地计算优化，但这里为了清晰单独存储）。