郑州哪家公司给国外做网站,上线了做的网站可以登陆,网站新媒体建设,行业门户网站 建站科技馆内有一台虚拟观景望远镜#xff0c;它可以用来观测特定纬度地区的地形情况。该纬度的海拔数据记于数组 heights #xff0c;其中 heights[i] 表示对应位置的海拔高度。请找出并返回望远镜视野范围 limit 内#xff0c;可以观测到的最高海拔值。
示例 1#xff1a; 输…科技馆内有一台虚拟观景望远镜它可以用来观测特定纬度地区的地形情况。该纬度的海拔数据记于数组 heights 其中 heights[i] 表示对应位置的海拔高度。请找出并返回望远镜视野范围 limit 内可以观测到的最高海拔值。
示例 1 输入heights [14,2,27,-5,28,13,39], limit 3 输出[27,27,28,28,39] 解释 滑动窗口的位置 最大值 [14 2 27] -5 28 13 39 27 14 [2 27 -5] 28 13 39 27 14 2 [27 -5 28] 13 39 28 14 2 27 [-5 28 13] 39 28 14 2 27 -5 [28 13 39] 39
提示 你可以假设输入总是有效的在输入数组不为空的情况下 1 limit heights.length -10000 heights[i] 10000
解法一
从头到尾遍历每个状态的窗口
class Solution {
public:vectorint maxAltitude(vectorint heights, int limit) {vectorint res;if(heights.empty()) return res;int max_;for(int i 0;i int(heights.size())-limit;i){max_ heights[i];for(int j 1;j limit;j){if(heights[ij] max_) max_ heights[ij];}res.push_back(max_);}return res;}
};解法二
上一个方法显然有很多冗余的比较比如
7 2 8 10
3滑动到第二个状态的时候因为8所在的位置在窗口左侧的右边所以只需要将新加入的10和8之前的最大值比较
8 2 6 4
3滑动到第二个状态的时候因为8所在的位置在窗口左侧所以需要重新在新窗口中找最大值 基于以上思想
class Solution {
public:vectorint maxAltitude(vectorint heights, int limit) {vectorint res;if(heights.empty()) return res;if(limit 1) return heights;int len heights.size(), pre_max_index 0, max_ heights[0];//计算第一个maxfor(int i 0;i limit;i){if(heights[i] max_){max_ heights[i];pre_max_index i;} }res.push_back(max_);for(int i 1;i len-limit;i){if(i pre_max_index){//如果这次窗口左侧在之前最大值的索引左侧不包括之前最大值的索引//只需要比较新加入的值和之前最大值if(heights[ilimit-1] max_){max_ heights[ilimit-1];pre_max_index ilimit-1;}res.push_back(max_);} else {//重新开始一个最大值默认值为heights[i]int temp limit;max_ heights[i];pre_max_index i;while(temp--){if(heights[itemp] max_){pre_max_index itemp;max_ heights[itemp];}}res.push_back(max_);}}return res;}
};当然如果limit为1根本就不需要计算直接返回就行。 新加入的值 h e i g h t s [ i l i m i t − 1 ] heights[ilimit-1] heights[ilimit−1]
