本文主要是介绍【九十】【算法分析与设计】单调队列,239. 滑动窗口最大值,1438. 绝对差不超过限制的最长连续子数组,[USACO12MAR] Flowerpot S，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
239. 滑动窗口最大值 - 力扣（LeetCode）
给你一个整数数组
nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1 输出：[1]
提示：
1 <= nums.length <= 10(5)
-10(4) <= nums[i] <= 10(4)
1 <= k <= nums.length
1.
利用递归的思维去写迭代,结合while循环,将出口条件写入while循环判断里面,对于每一个出口条件两两之间是&&连接.其次对于每一个单独的出口条件前面都需要加上一个取反!.
2.
利用单调队列存储区间中最大值信息.
[l,r)左闭右开.
3.
考虑将r位置元素加入区间中,先维护区间的单调性,维护完直接尾插r位置元素.
考虑将l位置元素移除区间,如果对头的下标和过期的元素相同就头删.
class Solution {
public:vector<int>arr;//下标对应元素int k;//区间的长度int n;//元素的个数int l,r;//左右区间下标deque<int>dq;//单调队列存储区间最大值vector<int>ret;//结果数组void init(){n=arr.size();//初始化元素个数while(!(r-l==k)){//当前节点信息是l,r//出口的条件,r-l==kwhile(!dq.empty()&&!(arr[r]<arr[dq.back()])){//出口条件,队列空,或者r进来的元素小于队列尾元素,也就是队列保证单调性//r进来元素也可以保持单调性dq.pop_back();}dq.push_back(r);++r;}ret.push_back(arr[dq.front()]);//维护结果数组}void solve(){while(!(r==n)){//出口条件,r==nwhile(!(dq.empty())&&!(arr[r]<arr[dq.back()])){//出口条件,队列空或者栈能够维持单调性dq.pop_back();}dq.push_back(r);if(dq.front()==l)dq.pop_front();//如果过期元素下标l等于队列头元素下标,头删++r,++l;ret.push_back(arr[dq.front()]);}}vector<int> maxSlidingWindow(vector<int>& _nums, int _k) {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);arr=_nums,k=_k;init();solve();return ret;}
};1438. 绝对差不超过限制的最长连续子数组 - 力扣（LeetCode）
给你一个整数数组
nums，和一个表示限制的整数limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于limit。如果不存在满足条件的子数组，则返回
0。示例 1：
输入：nums = [8,2,4,7], limit = 4 输出：2 解释：所有子数组如下： [8] 最大绝对差 |8-8| = 0 <= 4. [8,2] 最大绝对差 |8-2| = 6 > 4. [8,2,4] 最大绝对差 |8-2| = 6 > 4. [8,2,4,7] 最大绝对差 |8-2| = 6 > 4. [2] 最大绝对差 |2-2| = 0 <= 4. [2,4] 最大绝对差 |2-4| = 2 <= 4. [2,4,7] 最大绝对差 |2-7| = 5 > 4. [4] 最大绝对差 |4-4| = 0 <= 4. [4,7] 最大绝对差 |4-7| = 3 <= 4. [7] 最大绝对差 |7-7| = 0 <= 4. 因此，满足题意的最长子数组的长度为 2 。
示例 2：
输入：nums = [10,1,2,4,7,2], limit = 5 输出：4 解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。
示例 3：
输入：nums = [4,2,2,2,4,4,2,2], limit = 0 输出：3
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9
class Solution {
public:vector<int> arr; // 存储输入的数组int n; // 数组的长度int limit; // 允许的最大绝对差限制int ret; // 存储最长子数组的长度int l, r; // 滑动窗口的左右边界，[l, r)deque<int> dq_max; // 双端队列，用于存储窗口内最大值的索引deque<int> dq_min; // 双端队列，用于存储窗口内最小值的索引void init() { // 初始化函数n = arr.size(); // 获取数组长度l = r = 0; // 初始化左右窗口边界}void solve() { // 主处理函数while (r != n) { // 当右边界没有达到数组尾部时while (!dq_max.empty() && !(arr[dq_max.back()] > arr[r])) {dq_max.pop_back(); // 维护最大值队列，保持队列单调递减}while (!dq_min.empty() && !(arr[dq_min.back()] < arr[r])) {dq_min.pop_back(); // 维护最小值队列，保持队列单调递增}dq_max.push_back(r); // 将当前元素索引加入最大值队列dq_min.push_back(r); // 将当前元素索引加入最小值队列r++; // 扩大右边界if (abs(arr[dq_max.front()] - arr[dq_min.front()]) > limit) { // 如果当前窗口的最大最小值差超过限制if (dq_max.front() == l)dq_max.pop_front(); // 如果最大值是窗口左边界，从队列中移除if (dq_min.front() == l)dq_min.pop_front(); // 如果最小值是窗口左边界，从队列中移除l++; // 缩小左边界}cout << arr[dq_max.front()] << " " << arr[dq_min.front()] << endl; // 输出当前窗口的最大值和最小值ret = max(ret, r - l); // 更新最长子数组的长度}}int longestSubarray(vector<int>& _nums, int _limit) {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 优化输入输出arr = _nums, limit = _limit; // 初始化数组和限制init(); // 调用初始化函数solve(); // 调用处理函数return ret; // 返回结果}
};
[USACO12MAR] Flowerpot S - 洛谷
[USACO12MAR] Flowerpot S
题目描述
Farmer John has been having trouble making his plants grow, and needs your help to water them properly. You are given the locations of N raindrops (1 <= N <= 100,000) in the 2D plane, where y represents vertical height of the drop, and x represents its location over a 1D number line:
!
Each drop falls downward (towards the x axis) at a rate of 1 unit per second. You would like to place Farmer John's flowerpot of width W somewhere along the x axis so that the difference in time between the first raindrop to hit the flowerpot and the last raindrop to hit the flowerpot is at least some amount D (so that the flowers in the pot receive plenty of water). A drop of water that lands just on the edge of the flowerpot counts as hitting the flowerpot.
Given the value of D and the locations of the N raindrops, please compute the minimum possible value of W.
老板需要你帮忙浇花。给出 $$$$ 滴水的坐标，$y$ 表示水滴的高度，$x$ 表示它下落到 $$$$ 轴的位置。
每滴水以每秒 $$$$ 个单位长度的速度下落。你需要把花盆放在 $$$$ 轴上的某个位置，使得从被花盆接着的第 $$$$ 滴水开始，到被花盆接着的最后 $$$$ 滴水结束，之间的时间差至少为 $D$。
我们认为，只要水滴落到 $$$$ 轴上，与花盆的边沿对齐，就认为被接住。给出 $$$$ 滴水的坐标和 $$$$ 的大小，请算出最小的花盆的宽度 $W$。
输入格式
第一行 $$$$ 个整数 $$$$ 和 $D$。
接下来 $$$$ 行每行 $$$$ 个整数，表示水滴的坐标 $(x,y)$。
输出格式
仅一行 $$$$ 个整数，表示最小的花盆的宽度。如果无法构造出足够宽的花盆，使得在 $$$$ 单位的时间接住满足要求的水滴，则输出 $-1$。
样例 #1
样例输入 #1
4 5 6 3 2 4 4 10 12 15样例输出 #1
2提示
有 $$$$ 滴水，$(6,3)$ ，$(2,4)$ ，$(4,10)$ ，$(12,15)$ 。水滴必须用至少 $$$$ 秒时间落入花盆。花盆的宽度为 $$$$ 是必须且足够的。把花盆放在 $$x=4\dots$$ 的位置，它可以接到 $$$$ 和 $$$$ 水滴, 之间的时间差为 $$10-3=$$ 满足条件。
【数据范围】
$$40\$$ 的数据：$1 \le N \le 1000$ ，$1 \le D \le 2000$ 。
$$100\$$ 的数据：$1 \le N \le 10 ^ 5$ ，$1 \le D \le 10 ^ 6$ ，$0\le x,y\le10^6$ 。
1.
struct _compare {bool operator()(const p& a, const p& b)const {return a.first < b.first;}
};这个版本仅比较 pair 元素的第一个值，即 x 坐标。它不考虑 y 坐标的值。这意味着如果有多个点具有相同的 x 坐标，它们之间的顺序是未定义的（取决于底层容器如 map 的行为）。这可能导致不稳定的排序结果，如果 map 或 set 在插入时已经包含相同的 x 值，可能不会插入新的元素。
struct _compare {bool operator()(const p& a, const p& b) const {if (a.first == b.first) return a.second > b.second; // 如果x相同，比较yreturn a.first < b.first;}
};这个版本比较了 pair 的 x 值，如果它们相同，则会根据 y 值进行比较.
2.
坐标压缩,利用map绑定坐标和高度信息和下标.
利用vector得到下标到坐标和高度信息的索引.
map是由坐标和高度得到对应的下标.
vector是由下标得到坐标和高度信息.
3.
先将坐标和高度信息全部加入到map中,需要编写自定义排序的类class.
类class里面仿函数重载.用于判断前者是否在后者的前面.
4.
遍历排序后的map需要用范围for.然后依次填入索引.
此时维护vector.
#if 1
// 引入常用的头文件
#include<bits/stdc++.h>
using namespace std;#define int long long // 使用宏定义将int定义为long long类型，以支持更大的数值
#define p pair<int,int> // 使用宏定义简化pair<int,int>的书写
#define MOD 1e9+7 // 定义一个常用的模数
#define endl '\n' // 定义换行符为'\n'，提高输出效率/*
struct _compare {bool operator()(const p& a, const p& b)const {return a.first < b.first;}
};
*/// 自定义比较结构体，用于排序pair
struct _compare {bool operator()(const p& a, const p& b) const {if (a.first == b.first) return a.second > b.second; // 如果x坐标相同，则按y坐标降序排列return a.first < b.first; // 否则按x坐标升序排列}
};int n, d; // 声明总水滴数n和时间差d
map<p, int, _compare> p_id; // 使用map，键为水滴坐标，值为索引，自定义比较规则
vector<p> id_val; // 存储从map中提取的水滴坐标
int ret; // 存储最终结果，即最小花盆宽度
deque<int> dq_max; // 双端队列，用于维护窗口内的最大值
deque<int> dq_min; // 双端队列，用于维护窗口内的最小值
int l, r; // 滑动窗口的左右指针// 初始化函数，从map中提取数据到vector，初始化变量
void init() {int i = 0;for (auto& x : p_id) { // 遍历mapx.second = i++; // 给每个元素分配一个唯一的索引id_val.push_back(x.first); // 将坐标添加到vector}ret = LLONG_MAX; // 初始化结果为最大长整型值，方便后续取最小值
}// 处理函数，寻找最小花盆宽度
void solve() {while (!(r == id_val.size())) { // 当右指针没有越界时while (!(dq_max.empty()) && !(id_val[r].second < id_val[dq_max.back()].second)) {dq_max.pop_back(); // 维护最大值队列，确保队列单调递减}while (!(dq_min.empty()) && !(id_val[r].second > id_val[dq_min.back()].second)) {dq_min.pop_back(); // 维护最小值队列，确保队列单调递增}dq_max.push_back(r); // 将当前索引加入最大值队列dq_min.push_back(r); // 将当前索引加入最小值队列r++; // 右指针右移while (id_val[dq_max.front()].second - id_val[dq_min.front()].second >= d) { // 检查当前窗口是否满足条件ret = min(ret, abs(id_val[dq_max.front()].first - id_val[dq_min.front()].first)); // 更新结果if (dq_max.front() == l) dq_max.pop_front(); // 如果最大值索引为左指针，出队if (dq_min.front() == l) dq_min.pop_front(); // 如果最小值索引为左指针，出队l++; // 左指针右移}}cout << (ret==LLONG_MAX ? -1 : ret); // 输出结果，如果未更新则返回-1}// 主函数
signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 加速输入输出cin >> n >> d; // 输入水滴总数和时间差for (int i = 0; i < n; i++) {p tmp_p; cin >> tmp_p.first >> tmp_p.second; // 输入每个水滴的坐标p_id[tmp_p]; // 将坐标插入map，由于不重复，不需要指定值}init(); // 调用初始化函数，准备数据solve(); // 调用处理函数，寻找最小花盆宽度return 0; // 程序正常结束
}
#endif // 1
结尾
最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。
同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。
谢谢您的支持，期待与您在下一篇文章中再次相遇！
这篇关于【九十】【算法分析与设计】单调队列,239. 滑动窗口最大值,1438. 绝对差不超过限制的最长连续子数组,[USACO12MAR] Flowerpot S的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
