資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中將陣列分成有序塊的最大數量
假設我們給出一個數組 arr，它是 [0, 1, ..., arr.length - 1] 的排列，我們必須將陣列分成幾個“塊”或分割槽，並分別對每個分割槽進行排序。因此，在連線它們之後，結果將是有序陣列。如果陣列類似於 [1,0,2,3,4]，則輸出為 4，因為我們可以將其分成兩個分割槽，例如 [1, 0] 和 [2,3,4]，但這也可以是 [1, 0]，[2]，[3]，[4]。這是可能的最高塊數，因此輸出為 4。
我們最多可以建立多少個塊？
為了解決這個問題，我們將遵循以下步驟：
- ans := 0, minVal := inf, n := arr 的大小, maxVal := -inf
- 對於 i 從 0 到 n
- maxVal := arr[i] 和 maxVal 的最大值
- 如果 maxVal = i，則將 ans 加 1
- 返回 ans
示例
讓我們來看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
int ans = 0;
int minVal = INT_MAX;
int n = arr.size();
int maxVal = INT_MIN;
for(int i = 0; i < n; i++){
maxVal = max(arr[i], maxVal);
if(maxVal == i){
ans++;
}
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,0,2,3,4};
cout << (ob.maxChunksToSorted(v));
}輸入
[1,0,2,3,4]
輸出
4
更新於：2020年4月29日
396 次瀏覽
廣告