資料結構
網路
關係型資料庫管理系統
作業系統
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) 空間複雜度內獲得了峰值。
121 次瀏覽
