作者推荐
涉及知识点
单调栈 排序 map 区间合并
题目
给你一个整数数组 arr 。
将 arr 分割成若干 块 ，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。
返回能将数组分成的最多块数？
示例 1：
输入：arr = [5,4,3,2,1]
输出：1
解释：
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。
示例 2：
输入：arr = [2,1,3,4,4]
输出：4
解释：
可以把它分成两块，例如 [2, 1], [3, 4, 4]。
然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。
参数范围：
1 <= arr.length <= 2000
0 <= arr[i] <= 108
单调栈
排序后，各块的最小值，一定大于等于前一个块的最大值。我们无需记录各块的最小值，只需要记录各块的最大值。
| 新加的数如果大于所有已有块的最大值 | 自成一组 |
| 新加的数如果小于若干块的最大值 | 这些块和新加的数合并成一组 |
| 新加的数等于某个块的最大值，不小于任何块的最大值 | 自称一组 |
| 新加的数等于某个块的最大值，小于某些块的最大值 | 和小于的块合并 |
综上所述： 新加的值和它小于的块合并。后面块的最大值，一定大于等于前面块的最大值。否则：合并了。
代码
核心代码
class Solution { public: int maxChunksToSorted(vector<int>& arr) { stack<int> staMax; int i = 0; { const int iMin = *std::min_element(arr.begin(), arr.end()); int iMax = INT_MIN; for (; i < arr.size(); i++) { iMax = max(iMax, arr[i]); if (iMin == arr[i]) { staMax.emplace(iMax); i++; break; } } } for (; i < arr.size(); i++) { const int iMax = max(arr[i], staMax.top()); while (staMax.size()&&(arr[i] < staMax.top())) { staMax.pop(); } staMax.emplace(iMax); } return staMax.size(); } };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<int> arr; { Solution slu; arr = { 5, 4, 3, 2, 1 }; auto res = slu.maxChunksToSorted(arr); Assert(1, res); } { Solution slu; arr = { 2,1,3,4,4 }; auto res = slu.maxChunksToSorted(arr); Assert(4, res); } { Solution slu; arr = { 4, 2, 2, 1, 1 }; auto res = slu.maxChunksToSorted(arr); Assert(1, res); } //CConsole::Out(res); }
其实第一块不用特殊处理
class Solution { public: int maxChunksToSorted(vector<int>& arr) { stack<int> staMax; for (int i = 0 ; i < arr.size(); i++) { int iMax = arr[i]; if (staMax.size()) { iMax = max(iMax, staMax.top()); } while (staMax.size()&&(arr[i] < staMax.top())) { staMax.pop(); } staMax.emplace(iMax); } return staMax.size(); } };
2023年3月版
class Solution { public: int maxChunksToSorted(vector& arr) { std::multiset setAll(arr.begin(), arr.end()); std::multiset setLeft; int iNum = 1; for (const auto& i : arr) { setAll.erase(setAll.find(i)); setLeft.insert(i); if (setAll.empty()) { continue; } if (*setLeft.rbegin() <= *setAll.begin()) { iNum++; } } return iNum; } };
区间合并（分块）+map(哈希映射)
| vSort | 对arr排序后的数据 |
| mValueNum | 键：arr(vSort)的值；值：数量。 arr[i]的值+1，vSort[i]的值减少1。如果数量为0，则删除键。 |
如果mValueNum的数量为0说明可以分块。假定前一个块的最后一个元素的下标是pre，则mValueNum记录的是各数值在vSort(pre,i]中出现的次数减去arr(pre,i]中出现的次数。
时间复杂度:预处理（排序）o(nlogn) 处理O(n)。
代码
class Solution { public: int maxChunksToSorted(vector<int>& arr) { vector<int> vSort = arr; sort(vSort.begin(), vSort.end()); unordered_map<int, int> mValueNum; int iRet = 0; for (int i = 0; i < arr.size(); i++) { auto Add = [&mValueNum](int key,int iValue) { mValueNum[key] += iValue; if (0 == mValueNum[key]) { mValueNum.erase(key); } }; Add(arr[i], 1); Add(vSort[i], -1); if (mValueNum.empty()) { iRet++; } } return iRet; } };
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用C++ 实现。
