请选择 进入手机版 | 继续访问电脑版
MSIPO技术圈 首页 IT技术 查看内容

2023-07-12力扣今日三题

2023-07-13

链接:

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;
}

限制:

  • 链表中节点的数量在范围 [2, 105]
  • 1 <= Node.val <= 105

相关阅读

热门文章

    手机版|MSIPO技术圈 皖ICP备19022944号-2

    Copyright © 2024, msipo.com

    返回顶部