資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中將陣列分成多個排序塊的最大數量
假設我們有一個包含整數的陣列 arr，我們需要將陣列分成幾個分割槽，並分別對每個分割槽進行排序。現在，在將它們連線起來後，我們將得到一個排序後的陣列。我們需要找到我們可以建立的最大分割槽數？
因此，如果輸入類似於 [3,2,4,5,5]，則輸出將為 4，因為我們可以建立 [3,2]、[4]、[5]、[5] 這樣的分割槽。
為了解決這個問題，我們將遵循以下步驟 -
cnt := 1
n := arr 的大小
定義一個大小為 n 的陣列 maxOfLeft
定義一個大小為 n 的陣列 minOfRight
maxOfLeft[0] := arr[0]
對於初始化 i := 1，當 i < n 時，更新（將 i 增加 1），執行 -
maxOfLeft[i] := maxOfLeft[i - 1] 和 arr[i] 中的最大值
minOfRight[n - 1] = arr[n - 1]
對於初始化 i := n - 2，當 i >= 0 時，更新（將 i 減小 1），執行 -
minOfRight[i] := minOfRight[i + 1] 和 arr[i] 中的最小值
對於初始化 i := 0，當 i < n - 1 時，更新（將 i 增加 1），執行 -
如果 minOfRight[i + 1] >= maxOfLeft[i]，則 -
(將 cnt 增加 1)
返回 cnt
讓我們看看以下實現以更好地理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
int cnt = 1;
int n = arr.size();
vector<int> maxOfLeft(n);
vector<int> minOfRight(n);
maxOfLeft[0] = arr[0];
for (int i = 1; i < n; i++)
maxOfLeft[i] = max(maxOfLeft[i - 1], arr[i]);
minOfRight[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
minOfRight[i] = min(minOfRight[i + 1], arr[i]);
for (int i = 0; i < n - 1; i++) {
if (minOfRight[i + 1] >= maxOfLeft[i])
cnt++;
}
return cnt;
}
};
main(){
Solution ob;
vector<int> v = {3,2,4,5,5};
cout << (ob.maxChunksToSorted(v));
}輸入
{3,2,4,5,5}輸出
4
更新於: 2020年6月8日
198 次檢視
廣告