数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究给定链表中峰值之间的最大距离
链表是一种线性数据结构，它将数据存储在节点中，每个节点包含下一个节点的地址以建立连接。峰值或峰值节点是指不在第一个或最后一个位置并且其值严格大于两个相邻节点的节点。由于可能存在多个峰值，我们必须找到两个连续峰值之间的最大距离。
示例
输入
Given Linked list: 1 -> 2 -> 3 -> 2 -> 7 -> 1 -> 6 -> 9 -> 8 -> NULL
输出
2
解释：这里我们在第三个节点（3）、第五个节点（7）和第八个节点（9）处有峰值。第三个节点和第五个节点之间的差值为 1，而第五个节点和第八个节点之间的差值为 2，因此我们将返回 2。
输入
Given Linked list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
输出
0
解释：这里，所有节点的值都按升序排列，因此这里没有峰值。所以，我们将返回 0。
方法
我们已经看到了上面给定问题的示例，现在我们将转向实现代码所需的步骤。
首先，我们将创建一个类来创建链表的节点块，并在类中，我们将定义一个整数来存储值，一个指针来存储下一个指针的地址，以及一个构造函数来初始化节点。
我们将创建一个函数，该函数将以链表的头节点作为参数，并返回所需的值作为返回值。
我们将创建一个临时指针指向头节点，然后使用它通过 while 循环遍历链表。
我们将检查当前节点是否为峰值，如果它是峰值，那么我们将计算它与前一个峰值（如果有）的距离，并更新答案和前一个峰值的值，然后移动到下一个节点。
在主函数中，我们将创建链表并调用函数以获取和打印答案。
示例
#include <bits/stdc++.h>
using namespace std;
// creating class for nodes
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;
}
// function to get the required distance
int findDistance(Node* head){
Node* temp = head; // temporary variable to traverse over the linked list
// variables to store current and previous peak
int curP = -1, prevP = -1;
int ans = 0;
// variable to store the previous element. we will make it int max as we will compare it to the current element to handle the edge case for the first node we will make it int max
int prev = INT_MAX;
int cur = 0; // variable to get the node number
while(temp->next != nullptr){
// if the current node is at peak
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(){
// creating head of the linked list
Node* head = new Node(1, NULL);
// adding data to the linked list
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<<"The given linked list is: "<<endl;
printLL(head);
cout<<"The distance between the two peaks of the given linked list is: "<<findDistance(head)<<endl;
}
输出
The given linked list is: 1 -> 2 -> 3 -> 2 -> 7 -> 1 -> 6 -> 9 -> 8 -> NULL The distance between the two peaks of the given linked list is: 2
时间和空间复杂度
上面代码的时间复杂度为 O(N)，其中 N 是给定链表中存在的节点数。我们只遍历链表一次，从而产生线性时间复杂度。
我们这里没有使用任何额外的空间，这使得空间复杂度为常数，即 O(1)。
结论
在这个问题中，我们给定一个链表，我们需要找到给定链表中两个连续峰值之间的距离。峰值是指其值严格大于其相邻节点的值的节点，并且它不能是给定链表的第一个或最后一个节点。我们已经遍历了链表并在 O(N) 时间和 O(1) 空间复杂度内获得了峰值。
更新于: 2023年8月31日
121 次浏览
广告