C++刷剑指offer（面试题59 - I. 滑动窗口的最大值）【滑动窗口】
本帖最后由 糖逗 于 2020-5-8 17:21 编辑题目出处：leetcode
面试题59 - I. 滑动窗口的最大值
题目描述：
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = , 和 k = 3
输出:
解释:
滑动窗口的位置 最大值
--------------- -----
-35367 3
1 5367 3
13 [-1-35] 367 5
13-1 [-353] 67 5
13-1-3 7 6
13-1-35 7
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
vector<int> solution(vector<int>& input, int k){
vector<int> result;
deque<int> temp;
int front_arrow = 0;
if(input.size() == 0 || k == 1) return input;
for(int i = 0; i < input.size(); i++){
if(temp.empty()){
temp.push_back(i);
continue;
};
if(input >= input){
temp.clear();
temp.push_front(i);
}
else{
while(input >= input){
temp.pop_back();
}
temp.push_back(i);
}
while(temp.front() <= i - k){
temp.pop_front();
}
if(i >= k - 1){
result.push_back(input);
}
}
return result;
}
int main(void){
int num;
cout << "send vector" << endl;
vector<int> list;
while(cin >> num)
{
list.push_back(num);
}
cout << endl;
cout << "send k" <<endl;
cin.clear();
int k;
cin >> k;
vector<int> result;
result = solution(list, k);
for(int i = 0; i < result.size(); i++){
cout << result;
}
cout << endl;
return 0;
}
参考链接：
https://www.bilibili.com/video/BV1rE411L77c?from=search&seid=1078736512342441171
https://blog.csdn.net/Chnyac/article/details/82710050
注意事项：
1.检查当前最大值是否在滑动窗口内。
2.deque双向队列中存储的是当前值的下标序号。
相同思路的题：面试题59 - II. 队列的最大值
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
示例 1：
输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],,,[],[],[]]
输出:
示例 2：
输入:
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出:
限制：
1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5
class MaxQueue {
public:
queue<int> input;
deque<int> temp;
MaxQueue() {
}
int max_value() {
if(temp.empty()) return -1;
else{
return temp.front();
}
}
void push_back(int value) {
input.push(value);
if(temp.empty()) temp.push_back(value);
else{
if(value >= temp.front()){
temp.clear();
temp.push_front(value);
}
else{
while(value >= temp.back()){
temp.pop_back();
}
temp.push_back(value);
}
}
}
int pop_front() {
if(input.empty()) return -1;
int result;
result = input.front();
input.pop();
if(result == temp.front()){
temp.pop_front();
}
return result;
}
};
/**
* Your MaxQueue object will be instantiated and called as such:
* MaxQueue* obj = new MaxQueue();
* int param_1 = obj->max_value();
* obj->push_back(value);
* int param_3 = obj->pop_front();
*/
相同思路的题：面试题63. 股票的最大利润
题目描述：假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例 1:
输入:
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入:
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
。
#include<iostream>
#include<deque>
#include<vector>
using namespace std;
int solution(vector<int>& input){
deque<int> temp;
if(input.size() == 0) return 0;
int compare = 0;
for(int i = 0; i < input.size(); i++){
if(temp.empty()) temp.push_back(input);
else{
if(input < temp.back()){
compare = (temp.front() - temp.back()) > compare ? temp.front() - temp.back() : compare;
temp.clear();
temp.push_back(input);
}
if(input > temp.front()){
temp.push_front(input);
}
}
}
compare = (temp.front() - temp.back()) > compare ? temp.front() - temp.back() : compare;
return compare;
}
int main(void){
int number;
vector<int> input;
int result;
while(cin >> number){
input.push_back(number);
}
result = solution(input);
cout << result << endl;
return 0;
}
这道出题高频 剑指 Offer 59 - I. 滑动窗口的最大值（双指针）
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int left = 0, right = 0;
vector<int> res;
int len = nums.size();
if(len == 0)return res;
while(left < len - k + 1){
int temp = nums;
while(right < len && right - left + 1 <= k){
temp = max(temp, nums);
right++;
}
left++;
res.push_back(temp);
right = left;
}
return res;
}
}; 可以 这道题 freeck2013 发表于 2021-10-15 14:14
可以 这道题
谢谢回评！{:10_254:}
页:
[1]