資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式查詢每個大小為k的連續子陣列的最大值
假設我們有一個包含n個元素的陣列和一個值k。我們需要找到每個大小為k的連續子陣列的最大值。
因此，如果輸入類似於arr = [3,4,6,2,8]，k = 3，則輸出將是大小為3的連續子陣列為[3,4,6]、[4,6,2]、[6,2,8]，因此最大元素為6、6和8。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個大小為k的雙端佇列Qi
- 初始化i := 0，當i < k時，更新（i加1），執行：
- 當Qi不為空且arr[i] >= arr[Qi的最後一個元素]時，執行：
- 從Qi刪除最後一個元素
- 將i插入到Qi的末尾
- 當Qi不為空且arr[i] >= arr[Qi的最後一個元素]時，執行：
- 對於i < arr的大小，更新（i加1），執行：
- 顯示arr[Qi的第一個元素]
- 當Qi不為空且Qi的第一個元素 <= i - k時，執行：
- 從Qi刪除第一個元素
- 當Qi不為空且arr[i] >= arr[Qi的最後一個元素]時，執行：
- 從Qi刪除最後一個元素
- 將i插入到Qi的末尾
- 顯示arr[Qi的第一個元素]
示例
讓我們看看下面的實現以獲得更好的理解：
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int main(){
vector<int> arr = {3,4,6,2,8};
int k = 3;
deque<int> Qi(k);
int i;
for (i = 0; i < k; ++i){
while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back();
Qi.push_back(i);
}
for ( ; i < arr.size(); ++i){
cout << arr[Qi.front()] << " ";
while ( (!Qi.empty()) && Qi.front() <= i - k)
Qi.pop_front();
while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back();
Qi.push_back(i);
}
cout << arr[Qi.front()] << endl;
}
輸入
{3,4,6,2,8}, 3輸出
6 6 8
更新於： 2021年10月7日
366 次瀏覽
廣告