C++ 给定链表中峰值的最大距离

链表是一种线性数据结构，它将数据存储在节点中，每个节点都包含下一个节点的地址以建立连接。峰值节点是不位于第一个或最后一个位置并且其值严格大于两个相邻节点的节点。我们需要找到连续两个峰值之间的最大距离，因为可能存在多个峰值。

样例示例

输入

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)空间复杂度下找到了峰值。