左神アルゴリズム学習日記——単調スタック

//                     （   ）           （   ）
int maxhist(vector hist)
{
	stack max;
	int res = INT_MIN;
	for (int i = 0; i < hist.size(); i++)
	{
		//       ，          ，      ，      ，          ，              
		while (!max.empty() && hist[max.top()] >= hist[i])
		{
			int h = hist[max.top()];
			max.pop();
			int l = max.size() == 0 ? -1 : max.top();
			res = std::max(res, (i - l - 1)*h);
		}
		max.push(i);
	}
	//                ，                             
	while (!max.empty())
	{
		int h = hist[max.top()];
		max.pop();
		int l = max.size() == 0 ? -1 : max.top();
		res = std::max(res, (int)(hist.size() - l - 1)*h);
	}
	return res;
}

int maxmat(vector> mat)
{
	vector hist = mat[0];
	int res = maxhist(hist);
	//           ，      ，         ，           
	for (int i = 1; i < mat.size(); i++)
	{
		for (int j = 0; j < hist.size(); j++)
			hist[j] = mat[i][j] == 0 ? 0 : hist[j] + 1;
		res = std::max(res, maxhist(hist));
	}
	return res;
}
//            ,                           
int getteam(int time)
{
	return time>1 ? time*(time - 1) / 2 : 0;
}
//      ，              
int getneigh(vector arr)
{
	int maxindex;
	for (int i = 0; i < arr.size(); i++)
	{
		maxindex = arr[maxindex] < arr[i] ? i : maxindex;//       
	}
	int res=0;
	stack> dull;
	dull.push({ arr[maxindex], 1 });//    ，       ，         ，            
	int index=(maxindex+1)%arr.size();
	while (index != maxindex)
	{
		while (arr[index]>dull.top().first)//            ，     ，                      ，                               
		{
			pair temp = dull.top();
			dull.pop();
			res += getteam(temp.second) + 2 * temp.second;
		}
		if (arr[index] == dull.top().first)
			dull.top().second++;
		else
			dull.push({ arr[index], 1 });
		index = (index + 1) % arr.size();
	}
	while (!dull.empty())
	{
		pair temp = dull.top();
		dull.pop();
		res += getteam(temp.second);
		if (!dull.empty())
		{
			res += temp.second;
			if (dull.size() > 1)//   2 ，              
				res += temp.second;
			else//   2 ，        ，      ，        
				res += dull.top().second > 1 ? temp.second:0;
		}
	}
}