2023-07-12力扣今日三题-Toy模板网

这篇具有很好参考价值的文章主要介绍了2023-07-12力扣今日三题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

链接：

2058. 找出临界点之间的最小和最大距离

题意：

链表

某个节点严格大于前后时，这个节点为局部极大值节点；某个节点严格小于前后时，这个节点为局部极小值节点

前提：必须前后均非空

找两个不同临界点的最大距离和最小距离

解：

一开始还以为要找极大和极小之间的最大最小，后来看了一下案例发现就是单纯的不同临界点

所以判断一下是否是临界点，然后存一下上一个临界点和第一个临界点下标就可以了

剩下都是一些基本链表操作

实际代码：

#include<bits/stdc++.h>
using namespace std;
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) {}
};
vector<int> nodesBetweenCriticalPoints(ListNode* head)
{
    vector<int> ans {INT_MAX,INT_MIN};
    int index_head=INT_MAX,index_pre=0;
    int t1=head->val,t2=0,t3=0;
    
    int mao=1;head=head->next;
    for(;head->next!=nullptr;mao++)
    {
        t2=head->val;t3=head->next->val;
        //cout<<mao<<":"<<t1<<" "<<t2<<" "<<t3<<endl;
        
        if(t3)//合规节点 
        {
            if( (t2<t1 && t2<t3) || (t2>t1 && t2>t3) )//局部极小值点 || 局部极大值点
            {
                if(index_pre)//存在上一个临界点
                {
                    ans[0]=min( ans[0] , abs(mao-index_pre) );
                }
                
                index_head=min(index_head,mao);
                index_pre=mao;
            }
        }
        
        head=head->next;t1=t2;
    }
    if(index_head==INT_MAX || index_head==index_pre)//没有 || 仅一个 
    {
        ans[0]=ans[1]=-1;
    }
    else ans[1]=abs(index_pre-index_head);
    
    return ans;
}
int main()
{
    ListNode* head=nullptr;
    ListNode* thead;
    int n;cin>>n;
    
    for(int f=1;f<=n;f++)
    {
        int temp;cin>>temp;
        if(f==1)
        {
            head=new ListNode(temp);
            thead=head;
        }
        else
        {
            head->next=new ListNode(temp);
            head=head->next;
        }
    }
    
    vector<int> ans=nodesBetweenCriticalPoints(thead);
    
    for(auto i :ans) cout<<i<<" ";
    return 0;
}

限制：文章来源地址https://www.toymoban.com/news/detail-554876.html