資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究大小為 K 的所有子陣列的最小元素和最大元素之和。
在這個問題中，我們需要獲取長度為 K 的所有子陣列的最大和最小元素，並將它們加起來得到答案。
第一個解決方案是遍歷所有大小為 K 的子陣列，找到每個子陣列的最小和最大元素，並將它們加起來。解決此問題的最佳化方法是使用雙端佇列資料結構。我們將在雙端佇列中儲存子陣列的最小和最大元素的索引。
問題陳述 - 我們給定一個包含 N 個正整數或負整數的陣列 nums[]。我們還給定了正整數 0 < K < N。我們需要對大小為 K 的所有子陣列的最大和最小元素進行求和。
示例
輸入
nums[] = {3, 5, −2, 6, 4, 8, −9, 10, −5}, K = 4
輸出
15
解釋 - 在這裡，我們給出了每個子陣列的最小和最大元素。
[3, 5, −2, 6] - min_ele = −2, max_ele = 6 -> min_ele + max_ele = 4
[5, −2, 6, 4] - min_ele = −2, max_ele = 6 -> min_ele + max_ele = 4
[−2, 6, 4, 8] - min_ele = −2, max_ele = 8 -> min_ele + max_ele = 6
[6, 4, 8, −9] - min_ele = −9, max_ele = 8 -> min_ele + max_ele = −1
[4, 8, −9, 10] - min_ele = −9, max_ele = 10 -> min_ele + max_ele = 1
[8, −9, 10, −5} - min_ele = −9, max_ele = 10 -> min_ele + max_ele = 1
因此，總和為 4 + 4 + 6 + −1 + 1 + 1 等於 15。
輸入
nums[] = {3, 5, −2, 6, 4, 8, −9, 10, −5}, K = 9
輸出
1
解釋 - K 等於陣列的大小。因此，我們可以對給定陣列的最小和最大元素求和，它們分別是 -9 和 10。
輸入
nums[] = {2, 7, −9}, K = 1
輸出
0
解釋 - K 的值為 1。因此，我們可以在總和中將每個元素加兩次。
方法 1
在這種方法中，我們將使用兩個巢狀迴圈來獲取長度為 K 的所有子陣列，並找到子陣列的最小和最大元素。之後，我們將所有子陣列的最小和最大元素加到結果變數中。
演算法
步驟 1 - 將 'ans' 初始化為 0 以儲存結果總和值。
步驟 2 - 開始遍歷給定陣列，並使用 'm' 變數初始化為 0 來跟蹤子陣列的長度。另外，使用 'max_ele' 變數初始化為最小整數值，使用 'min_ele' 變數初始化為最大整數值。
步驟 3 - 使用巢狀迴圈從第 p 個索引遍歷陣列。
步驟 3.1 - 將 'm' 值加 1。
步驟 3.2 - 使用 max() 函式從 nums[q] 和 max_ele 元素中獲取最大值。另外，使用 min() 函式從 nums[q] 和 min_ele 元素中獲取最小值。
步驟 3.3 - 如果 m 等於 K，則將 max_ele 和 min_ele 的值加到 'ans' 變數的值中，並使用 break 關鍵字中斷巢狀迴圈。
步驟 4 - 在函式結束時返回 'ans'。
示例
#include <bits/stdc++.h>
using namespace std;
int subArrSum(int nums[], int len, int K) {
// To store the resultant ans
int ans = 0;
// Get a subarray of size K
for (int p = 0; p < len; p++) {
int m = 0;
// For storing the minimum and maximum element of the subarray
int max_ele = INT_MIN;
int min_ele = INT_MAX;
for (int q = p; q < len; q++) {
m++;
max_ele = max(max_ele, nums[q]);
min_ele = min(min_ele, nums[q]);
// When we get a subarray of length K
if (m == K) {
ans += max_ele + min_ele;
break;
}
}
}
return ans;
}
int main() {
int nums[] = {3, 5, -2, 6, 4, 8, -9, 10, -5};
int len = sizeof(nums) / sizeof(nums[0]);
int K = 4;
cout << "The ans of minimum and maximum elements of all subarrays of size K is " << subArrSum(nums, len, K);
return 0;
}
輸出
The ans of minimum and maximum elements of all subarrays of size K is 15
時間複雜度 - O(N*K)，因為我們遍歷了長度為 K 的所有子陣列。
空間複雜度 - O(1)，因為我們使用了常數空間。
方法 2
在這種方法中，我們將使用雙端佇列資料結構來解決問題。我們將建立兩個不同的雙端佇列來跟蹤當前子陣列的最小和最大元素的索引。
演算法
步驟 1 - 將 'totalSum' 變數初始化為 0 以儲存結果總和。
步驟 2 - 定義大小為 K 的 'inc' 和 'dec' 雙端佇列以跟蹤子陣列元素的索引。'inc' 雙端佇列將用於根據子陣列元素的遞增值儲存陣列元素的索引，'dec' 雙端佇列將用於根據子陣列元素的遞減值儲存陣列元素的索引。
步驟 3 - 現在，將 'p' 初始化為 0，我們需要處理長度為 K 的第一個子陣列。
步驟 4 - 遍歷長度為 K 的第一個子陣列。
步驟 4.1 - 在迴圈中，使用 while 迴圈從 'inc' 雙端佇列中刪除元素，如果佇列不為空且陣列中 inc.back() 索引處的元素大於第 p 個索引處的元素。
步驟 4.2 - 同樣，如果陣列中 dec.back() 索引處的元素小於第 p 個索引處的元素，則從 'dec' 雙端佇列的末尾刪除元素。
步驟 4.3 - 將 p 推入 'inc' 和 'dec' 雙端佇列。
步驟 5 - 我們需要處理長度為 K 的其他子陣列。
步驟 5.1 - 從 'inc' 和 'dec' 雙端佇列中訪問第一個索引值，根據它們的第一個索引從陣列中獲取元素值，並將它們加到 'totalSum' 值中。
步驟 5.2 - 如果 'inc' 和 'dec' 雙端佇列的開頭存在任何索引不在當前視窗中，則將其從雙端佇列中彈出。
步驟 5.3 - 再次對其他子陣列遵循步驟 4.1 和 4.2。
步驟 5.4 - 將 p 推入兩個雙端佇列。
步驟 6 - 處理最後一個視窗的最小和最大元素的總和。
步驟 7 - 返回 'totalSum' 值。
示例
#include <bits/stdc++.h>
using namespace std;
int subArrSum(int nums[], int len, int k){
int totalSum = 0;
// Deques to store indices of the current window in increasing and decreasing order, respectively;
deque<int> inc(k), dec(k);
// Handling the first window
int p = 0;
for (p = 0; p < k; p++){
// Remove elements which are greater than the current element
while ((!inc.empty()) && nums[inc.back()] >= nums[p])
inc.pop_back();
// Remove elements from dec deque which are smaller than the current element
while ((!dec.empty()) && nums[dec.back()] <= nums[p])
dec.pop_back(); // Remove from rear
// Add the nums[p] at last
inc.push_back(p);
dec.push_back(p);
}
// Hanlding other windows
for (; p < len; p++){
// get the first element from both the queues, and add them
totalSum += nums[inc.front()] + nums[dec.front()];
// Removing elements of the previous window
while (!inc.empty() && inc.front() <= p - k)
inc.pop_front();
while (!dec.empty() && dec.front() <= p - k)
dec.pop_front();
while ((!inc.empty()) && nums[inc.back()] >= nums[p])
inc.pop_back();
while ((!dec.empty()) && nums[dec.back()] <= nums[p])
dec.pop_back();
inc.push_back(p);
dec.push_back(p);
}
// Last window sum
totalSum += nums[inc.front()] + nums[dec.front()];
return totalSum;
}
int main() {
int nums[] = {3, 5, -2, 6, 4, 8, -9, 10, -5};
int len = sizeof(nums) / sizeof(nums[0]);
int K = 4;
cout << "The ans of minimum and maximum elements of all subarrays of size K is " << subArrSum(nums, len, K);
return 0;
}
輸出
The ans of minimum and maximum elements of all subarrays of size K is 15
時間複雜度 - O(N + K)，遍歷陣列。
空間複雜度 - O(K)，在雙端佇列中儲存索引。
第二種方法在時間複雜度方面更加最佳化。但是，它比第一種方法佔用更多空間。程式設計師可以根據給定的元素數量使用任何方法。對於較小的輸入，第一種方法適用，而對於較大的輸入，第二種方法適用。
453 次瀏覽
