给定链表中峰之间的最大距离
data structurec++programming
链表是一种线性数据结构，它将数据存储在节点中，每个节点都包含下一个节点的地址以建立连接。峰或峰节点是指不出现在第一个或最后一个位置的节点，其值严格大于两个相邻节点的值。我们必须找到两个连续峰之间的最大距离，因为可能存在多个峰。
示例
输入
给定链表:1 -> 2 -> 3 -> 2 -> 7 -> 1 -> 6 -> 9 -> 8 -> NULL
输出
2
解释:这里我们在第三个节点 (3)、第五个节点 (7) 和第八个节点 (9) 处出现峰值。第三节点和第五个节点之间的差值为 1，而第五节点和第八个节点之间的差值为 2，因此我们返回 2。
输入
给定链表:1 -> 2 -> 3 -> 4 -> 5 -> NULL
输出
0
解释:这里所有节点的值都按升序排列，因此没有峰值。因此，我们将返回 0。
方法
我们已经看过上面给出的问题的示例，现在我们将进入实现代码所需的步骤:
首先，我们将创建一个类来创建链表的节点块，并在类中定义用于存储值的整数、用于存储下一个指针地址的指针以及用于初始化节点的构造函数。
我们将创建一个函数，该函数以链表的头部作为参数，并返回所需的值作为返回值。
我们将创建一个指向头节点的临时指针，然后使用它通过 while 循环遍历链表。
我们将检查当前节点是否为峰值，如果是峰值，则计算它与前一个峰值(如果有)的距离，并更新答案和前一个峰值的值，然后移动到下一个节点。
在主函数中，我们将创建链表，并调用该函数获取并打印答案。
示例
#include <bits/stdc++.h>
using namespace std;
// 创建节点类
class Node{
public:
int val;
Node* next;
// constructor
Node(int data, Node* next_ptr){
val = data;
next = next_ptr;
}
};
void printLL(Node* head){
Node* temp = head;
while(temp != nullptr){
cout<<temp->val<<" -> ";
temp = temp->next;
}
cout<<"NULL"<<endl;
}
// 获取所需距离的函数
int findDistance(Node* head){
Node* temp = head; // 用于遍历链表的临时变量
// 用于存储当前和前一个峰值的变量
int curP = -1, prevP = -1;
int ans = 0;
// 用于存储前一个元素的变量。我们将它设置为 int max，因为我们会将它与当前元素进行比较。为了处理第一个节点的极端情况，我们将它设置为 int max
int prev = INT_MAX;
int cur = 0; // 用于获取节点编号的变量
while(temp->next != nullptr){
// 如果当前节点处于峰值
if(temp->val > prev && temp->val > temp->next->val){
if(prevP == -1){
prevP = cur;
}
curP = cur;
ans = max(ans, curP-prevP-1);
prevP = curP;
}
prev = temp->val;
temp = temp->next;
cur ++;
}
return ans;
}
int main(){
// 创建链表的头部
Node* head = new Node(1, NULL);
// 将数据添加到链表
head->next = new Node(2, NULL);
head->next->next = new Node(3, NULL);
head->next->next->next = new Node(2, NULL);
head->next->next->next->next = new Node(7, NULL);
head->next->next->next->next->next = new Node(1, NULL);
head->next->next->next->next->next->next
= new Node(6, NULL);
head->next->next->next->next->next->next->next
= new Node(9, NULL);
head->next->next->next->next->next->next->next->next
= new Node(8, NULL);
cout<<"给定的链表是: "<<endl;
printLL(head);
cout<<"给定链表的两个峰值之间的距离是: "<<findDistance(head)<<endl;
}
输出
给定的链表是: 1 -> 2 -> 3 -> 2 -> 7 -> 1 -> 6 -> 9 -> 8 -> NULL 给定链表的两个峰值之间的距离是: 2
时间和空间复杂度
上述代码的时间复杂度为 O(N)，其中 N 是给定链表中节点的数量。我们只遍历链表一次，因此时间复杂度为线性。
这里我们没有使用任何额外的空间，因此空间复杂度为常数 O(1)。
结论
在这个问题中，我们给定一个链表，我们需要找到给定链表的两个连续峰值之间的距离。峰值是指其值严格大于其邻居值的节点，并且它不能是给定链表的第一个或最后一个节点。我们遍历了链表，并在 O(N) 时间和 O(1) 空间复杂度内找到了峰值。
