当前位置：首页 > news >正文

题解：AtCoder AT_awc0001_e Temperature Fluctuation Range

news 2026/4/23 21:28:01

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：E - Temperature Fluctuation Range

【题目描述】

Takahashi is analyzing weather data. There is a record of temperature observations taken overN NNconsecutive days in a certain region, where the temperature on dayi iiwasH i H_iHidegrees.
高桥正在分析天气数据。某个地区记录了连续N NN天的气温观测值，其中第i ii天的气温为H i H_iHi度。

Takahashi wants to select a consecutive period ofK KKdays from this observation data and investigate the temperature variation range during that period.
高桥希望从这些观测数据中选取连续K KK天的时间段，并研究该时间段内的气温变化范围。

Here, the “temperature variation range” for a consecutive period ofK KKdays is defined as the difference between the maximum temperature and the minimum temperature during that period.
此处，连续K KK天时间段的"气温变化范围"定义为该时间段内最高气温与最低气温的差值。

Takahashi wants to find a consecutive period ofK KKdays that maximizes the temperature variation range. Find the maximum value of the temperature variation range.
高桥希望找到一个连续K KK天的时间段，使得气温变化范围最大。求气温变化范围的最大值。

【输入】

N NNK KK
H 1 H 2 … H N H_1\ H_2\ \dots\ H_NH1H2…HN

The first line containsN NN, representing the number of observation days, andK KK, representing the number of consecutive days to select, separated by a space.
The second line containsH 1 , H 2 , … , H N H_1,H_2,…,H_NH1,H2,…,HN, representing the temperature on each day, separated by spaces.

【输出】

Output the maximum value of the temperature variation range in one line.

【输入样例】

5 3 2 5 1 8 4

【输出样例】

【解题思路】

【算法标签】

#单调队列#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=200005;intn,k;// n: 数组长度，k: 滑动窗口大小inta[N];// 原始数组intans=-2e18;// 存储最大差值，初始化为极小值structNode{intv,idx;// v: 数值，idx: 索引};deque<Node>minq,maxq;// 双端队列：minq维护窗口最小值，maxq维护窗口最大值signedmain(){cin>>n>>k;// 读入数组长度和窗口大小for(inti=1;i<=n;i++){cin>>a[i];// 读入数组元素}for(inti=1;i<=n;i++)// 遍历数组{// 维护minq队列：移除窗口外的元素while(!minq.empty()&&minq.front().idx<=i-k){minq.pop_front();}// 维护maxq队列：移除窗口外的元素while(!maxq.empty()&&maxq.front().idx<=i-k){maxq.pop_front();}// 维护minq队列：保持队列单调递增while(!minq.empty()&&minq.back().v>=a[i]){minq.pop_back();}// 维护maxq队列：保持队列单调递减while(!maxq.empty()&&maxq.back().v<=a[i]){maxq.pop_back();}// 将当前元素加入两个队列minq.push_back({a[i],i});maxq.push_back({a[i],i});// 当窗口大小达到k时，计算当前窗口的最大差值if(i>=k){ans=max(ans,maxq.front().v-minq.front().v);}}cout<<ans<<endl;// 输出结果return0;}