题目描述:
给定一个长为 n 的整数序列 a1, a2, …, an,要求你计算出有多少个区间 [l, r] 满足 max{ai} 与 min{ai} 的差不超过 1。
输入格式:
第一行包含一个整数 n。
第二行包含 n 个整数,表示整数序列。
输出格式:
输出一个整数,表示答案。
数据范围:
1≤n≤1051≤ai≤109
设计思路:
此题思路还是比较简单的,其主要思路是滑动窗口。窗口范围[l,r]向右移动时,窗口对于最大值和最小值的影响也要随之移动。我们考虑变动右端点r,首先左端点l一定小于等于r,所以我们需要能够快速的找到当前窗口的最大值和最小值。这里考虑用STL中的set函数来解决。
程序流程图:
输入n,a1,a2,..,anset q;int res=0;int j=0;for(int i=0;i