【map】【单调栈 】LeetCode768: 最多能完成排序的块 II

作者推荐

【贪心算法】【中位贪心】.执行操作使频率分数最大

涉及知识点

单调栈 排序 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] <= 10⁸

单调栈

排序后，各块的最小值，一定大于等于前一个块的最大值。我们无需记录各块的最小值，只需要记录各块的最大值。

新加的数如果大于所有已有块的最大值	自成一组
新加的数如果小于若干块的最大值	这些块和新加的数合并成一组
新加的数等于某个块的最大值，不小于任何块的最大值	自称一组
新加的数等于某个块的最大值，小于某些块的最大值	和小于的块合并

综上所述： 新加的值和它小于的块合并。后面块的最大值，一定大于等于前面块的最大值。否则：合并了。

代码

核心代码

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;
	}
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用C++ 实现。