2058. 找出臨界點之間的最小和最大距離

2058. 找出臨界點之間的最小和最大距離

鏈表中的 臨界點 定義為一個 局部極大值點 或 局部極小值點 。

如果當前節點的值 嚴格大于 前一個節點和后一個節點,那么這個節點就是一個 局部極大值點 。

如果當前節點的值 嚴格小于 前一個節點和后一個節點,那么這個節點就是一個 局部極小值點 。

注意:節點只有在同時存在前一個節點和后一個節點的情況下,才能成為一個 局部極大值點 / 極小值點 。

給你一個鏈表 head ,返回一個長度為 2 的數組 [minDistance, maxDistance] ,其中 minDistance 是任意兩個不同臨界點之間的最小距離,maxDistance 是任意兩個不同臨界點之間的最大距離。如果臨界點少于兩個,則返回 [-1,-1] 。

  • 示例 1:

圖片.png

輸入:head = [3,1]
輸出:[-1,-1]
解釋:鏈表 [3,1] 中不存在臨界點。

  • 示例 2:

圖片.png

輸入:head = [5,3,1,2,5,1,2]
輸出:[1,3]
解釋:存在三個臨界點:

  • [5,3,1,2,5,1,2]:第三個節點是一個局部極小值點,因為 1 比 3 和 2 小。
  • [5,3,1,2,5,1,2]:第五個節點是一個局部極大值點,因為 5 比 2 和 1 大。
  • [5,3,1,2,5,1,2]:第六個節點是一個局部極小值點,因為 1 比 5 和 2 小。
    第五個節點和第六個節點之間距離最小。minDistance = 6 - 5 = 1 。
    第三個節點和第六個節點之間距離最大。maxDistance = 6 - 3 = 3 。
  • 示例 3:

圖片.png

輸入:head = [1,3,2,2,3,2,2,2,7]
輸出:[3,3]
解釋:存在兩個臨界點:

  • [1,3,2,2,3,2,2,2,7]:第二個節點是一個局部極大值點,因為 3 比 1 和 2 大。
  • [1,3,2,2,3,2,2,2,7]:第五個節點是一個局部極大值點,因為 3 比 2 和 2 大。
    最小和最大距離都存在于第二個節點和第五個節點之間。
    因此,minDistance 和 maxDistance 是 5 - 2 = 3 。
    注意,最后一個節點不算一個局部極大值點,因為它之后就沒有節點了。
  • 示例 4:

圖片.png

輸入:head = [2,3,3,2]
輸出:[-1,-1]
解釋:鏈表 [2,3,3,2] 中不存在臨界點。

提示:

  • 鏈表中節點的數量在范圍 [2, 10510^5105] 內
  • 1 <= Node.val <= 10510^5105

解題思路

維護當前遍歷節點的前兩個節點的值,加上當前節點,每次我們可以遍歷到三個值,因此我們就可以判斷第二個節點 是否為局部極大值點 或 局部極小值點了,將每個節點編號,使用數組存儲臨界點之間的下標,遍歷數組是任意兩個不同臨界點之間的最小距離,兩個不同臨界點之間的最大距離為數組首尾元素相減的差值

代碼

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:vector<int> nodesBetweenCriticalPoints(ListNode *head) {if (head== nullptr||head->next== nullptr)return vector<int>{-1,-1};int f(head->val),s(head->next->val);ListNode *h=head->next->next;int i(2);vector<int> idx;while (h!= nullptr){if ((s>h->val&&s>f)||(s<h->val&&s<f))idx.push_back(i);f=s;s=h->val;h=h->next;i++;}if (idx.size()<=1)return vector<int>{-1,-1};int m=idx[idx.size()-1]-idx[0];for (int j = 1; j <idx.size() ; ++j) {m=min(idx[j]-idx[j-1],m);}return vector<int>{m,idx[idx.size()-1]-idx[0]};}
};

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/389850.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/389850.shtml
英文地址,請注明出處:http://en.pswp.cn/news/389850.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

tb計算機存儲單位_如何節省數TB的云存儲

tb計算機存儲單位Whatever cloud provider a company may use, costs are always a factor that influences decision-making, and the way software is written. As a consequence, almost any approach that helps save costs is likely worth investigating.無論公司使用哪種…

nginx簡單代理配置

原文&#xff1a;https://my.oschina.net/wangnian/blog/791294 前言 Nginx ("engine x") 是一個高性能的HTTP和反向代理服務器&#xff0c;也是一個IMAP/POP3/SMTP服務器。Nginx是由Igor Sysoev為俄羅斯訪問量第二的Rambler.ru站點開發的&#xff0c;第一個公開版本…

2059. 轉化數字的最小運算數

2059. 轉化數字的最小運算數 給你一個下標從 0 開始的整數數組 nums &#xff0c;該數組由 互不相同 的數字組成。另給你兩個整數 start 和 goal 。 整數 x 的值最開始設為 start &#xff0c;你打算執行一些運算使 x 轉化為 goal 。你可以對數字 x 重復執行下述運算&#xf…

Django Rest Framework(一)

一、什么是RESTful REST與技術無關&#xff0c;代表一種軟件架構風格&#xff0c;REST是Representational State Transfer的簡稱&#xff0c;中文翻譯為“表征狀態轉移”。 REST從資源的角度審視整個網絡&#xff0c;它將分布在網絡中某個節點的資源通過URL進行標識&#xff0c…

光落在你臉上,可愛一如往常

沙沙野 https://www.ssyer.com讓作品遇見全世界圖片來自&#xff1a;沙沙野沙沙野 https://www.ssyer.com讓作品遇見全世界圖片來自&#xff1a;沙沙野沙沙野 https://www.ssyer.com讓作品遇見全世界圖片來自&#xff1a;沙沙野沙沙野 https://www.ssyer.com讓作品遇見全世界圖…

數據可視化機器學習工具在線_為什么您不能跳過學習數據可視化

數據可視化機器學習工具在線重點 (Top highlight)There’s no scarcity of posts online about ‘fancy’ data topics like data modelling and data engineering. But I’ve noticed their cousin, data visualization, barely gets the same amount of attention. Among dat…

2047. 句子中的有效單詞數

2047. 句子中的有效單詞數 句子僅由小寫字母&#xff08;‘a’ 到 ‘z’&#xff09;、數字&#xff08;‘0’ 到 ‘9’&#xff09;、連字符&#xff08;’-’&#xff09;、標點符號&#xff08;’!’、’.’ 和 ‘,’&#xff09;以及空格&#xff08;’ &#xff09;組成。…

fa

轉載于:https://www.cnblogs.com/smallpigger/p/9546173.html

python中nlp的庫_用于nlp的python中的網站數據清理

python中nlp的庫The most important step of any data-driven project is obtaining quality data. Without these preprocessing steps, the results of a project can easily be biased or completely misunderstood. Here, we will focus on cleaning data that is composed…

51Nod 1043 幸運號碼

1 #include <stdio.h>2 #include <algorithm>3 using namespace std;4 5 typedef long long ll;6 const int mod 1e9 7;7 int dp[1010][10000];8 // dp[i][j] : i 個數&#xff0c;組成總和為j 的數量9 10 int main() 11 { 12 int n; 13 scanf("%d…

一張圖看懂云棲大會·上海峰會重磅產品發布

2018云棲大會上海峰會上&#xff0c;阿里云重磅發布一批產品并宣布了新一輪的價格調整&#xff0c;再次用科技普惠廣大開發者和用戶&#xff0c;詳情見長圖。 了解更多產品請戳&#xff1a;https://yunqi.aliyun.com/2018/shanghai/product?spm5176.8142029.759399.2.a7236d3e…

488. 祖瑪游戲

488. 祖瑪游戲 你正在參與祖瑪游戲的一個變種。 在這個祖瑪游戲變體中&#xff0c;桌面上有 一排 彩球&#xff0c;每個球的顏色可能是&#xff1a;紅色 ‘R’、黃色 ‘Y’、藍色 ‘B’、綠色 ‘G’ 或白色 ‘W’ 。你的手中也有一些彩球。 你的目標是 清空 桌面上所有的球。…

【黑客免殺攻防】讀書筆記14 - 面向對象逆向-虛函數、MFC逆向

虛函數存在是為了克服類型域解決方案的缺陷&#xff0c;以使程序員可以在基類里聲明一些能夠在各個派生類里重新定義的函數。 1 識別簡單的虛函數 代碼示例&#xff1a; #include "stdafx.h" #include <Windows.h>class CObj { public:CObj():m_Obj_1(0xAAAAAA…

怎么看另一個電腦端口是否通_誰一個人睡覺另一個看看夫妻的睡眠習慣

怎么看另一個電腦端口是否通In 2014, FiveThirtyEight took a survey of about 1057 respondents to get a look at the (literal) sleeping habits of the American public beyond media portrayal. Some interesting notices: first, that about 45% of all couples sleep to…

495. 提莫攻擊

495. 提莫攻擊 在《英雄聯盟》的世界中&#xff0c;有一個叫 “提莫” 的英雄。他的攻擊可以讓敵方英雄艾希&#xff08;編者注&#xff1a;寒冰射手&#xff09;進入中毒狀態。 當提莫攻擊艾希&#xff0c;艾希的中毒狀態正好持續 duration 秒。 正式地講&#xff0c;提莫在…

Java基礎之Collection和Map

List&#xff1a;實現了collection接口&#xff0c;list可以重復&#xff0c;有順序 實現方式&#xff1a;3種&#xff0c;分別為&#xff1a;ArrayList&#xff0c;LinkedList&#xff0c;Vector。 三者的比較&#xff1a; ArrayList底層是一個動態數組&#xff0c;數組是使用…

20155320《網絡對抗》Exp4 惡意代碼分析

20155320《網絡對抗》Exp4 惡意代碼分析 【系統運行監控】 使用schtasks指令監控系統運行 首先在C盤目錄下建立一個netstatlog.bat文件&#xff08;由于是系統盤&#xff0c;所以從別的盤建一個然后拷過去&#xff09;&#xff0c;用來將記錄的聯網結果格式化輸出到netstatlog.…

tableau 自定義省份_在Tableau中使用自定義圖像映射

tableau 自定義省份We have been reading about all the ways to make our vizzes in Tableau with more creativity and appeal. During my weekly practice for creating viz as part of makeovermonday2020 community, I came across geographical data which in way requir…

2055. 蠟燭之間的盤子

2055. 蠟燭之間的盤子 給你一個長桌子&#xff0c;桌子上盤子和蠟燭排成一列。給你一個下標從 0 開始的字符串 s &#xff0c;它只包含字符 ‘’ 和 ‘|’ &#xff0c;其中 ’ 表示一個 盤子 &#xff0c;’|’ 表示一支 蠟燭 。 同時給你一個下標從 0 開始的二維整數數組 q…

Template、ItemsPanel、ItemContainerStyle、ItemTemplate

原文:Template、ItemsPanel、ItemContainerStyle、ItemTemplate先來看一張圖(網上下的圖&#xff0c;加了幾個字) 實在是有夠“亂”的&#xff0c;慢慢來理一下&#xff1b; 1、Template是指控件的樣式 在WPF中所有繼承自contentcontrol類的控件都含有此屬性&#xff0c;&#…