解题思路

这道题目要求我们根据给定的天际线高度数据，计算出形成该天际线所需的最少建筑物数量。天际线由一系列高度变化点描述，每个建筑物可以看作是一个连续的、高度相同的矩形区域。

1. 问题分析

• 输入：天际线的宽度和一系列高度变化点（x坐标严格递增）。
• 输出：最少需要的建筑物数量。
• 关键点：建筑物必须连续且高度相同，不同高度或断开的部分需要新的建筑物。

2. 核心思路

• 单调栈的应用：使用单调栈来维护当前的高度序列，确保栈中的高度是单调递增的。
• 高度变化的处理：当遇到一个比栈顶高度低的新高度时，弹出栈顶元素并增加建筑物计数，直到栈顶高度不大于新高度。
• 新高度的处理：如果新高度与栈顶高度不同，则将新高度压入栈中。

3. 具体步骤

1. 初始化：

   • 读取输入的天际线宽度和高度数据。
   • 初始化一个栈，用于维护当前的高度序列。
   • 在高度数组的首尾各添加一个高度0，以处理边界情况。

2. 遍历高度数据：

   • 对于每个高度点，检查是否比栈顶高度低。
   • 如果是，则弹出栈顶元素并增加建筑物计数，直到栈顶高度不大于当前高度。
   • 如果当前高度与栈顶高度不同，则将当前高度压入栈中。

3. 输出结果：

   • 最终得到的建筑物计数即为所需的最少建筑物数量。

4. 示例解析

• 输入：

  10 26
  1 1
  2 2
  5 1
  6 3
  8 1
  11 0
  15 2
  17 3
  20 2
  22 1
  

• 处理过程：
  • 高度序列：0, 1, 2, 1, 3, 1, 0, 2, 3, 2, 1, 0
  • 使用单调栈处理后，建筑物计数为6。

5. 时间复杂度

• 遍历高度数据：O(N)，其中N为高度点的数量。
• 栈操作：每个高度点最多入栈和出栈一次，因此栈操作的总时间复杂度也是O(N)。
• 总体复杂度：O(N)，适用于大规模数据（N ≤ 50,000）。

方法选择

• 单调栈：高效处理高度序列，确保在O(N)时间内解决问题。
• 边界处理：在高度数组的首尾添加0，简化边界条件的处理。

解决代码

#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<cctype>  
#include<cmath>  
#include<iostream>  
#include<sstream>  
#include<iterator>  
#include<algorithm>  
#include<string>  
#include<vector>  
#include<set>  
#include<map>  
#include<stack>  
#include<deque>  
#include<queue>  
#include<list>  
using namespace std;  
const double eps = 1e-8;  
typedef long long LL;  
typedef unsigned long long ULL;  
const int INF = 0x3f3f3f3f;  
const int INT_M_INF = 0x7f7f7f7f;  
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;  
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;  
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};  
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};  
const int MOD = 1e9 + 7;  
const double pi = acos(-1.0);  
const int MAXN=5010;  
const int MAXM=100010;
const int M=50010;  
int main()
{
	int n,m;
	while(scanf("%d%d",&m,&n)!=EOF)
	{
		int h[M];
		for(int i=1;i<=m;i++)
		{
			int a;
			scanf("%d%d",&a,&h[i]);
		}
		stack<int> s;
		h[0]=0;
		h[m+1]=0;
		while(!s.empty())
			s.pop();
		s.push(0);
		int ans=0;
		for(int i=1;i<=m+1;i++)    //n+1d的目的为就叫栈中元素全出来
		{
			while(!s.empty()&&h[s.top()]>h[i])  //若栈顶元素大于当前值，楼的位置就确定了
			{
				s.pop();
				ans++;
				
			}
			if(h[s.top()]!=h[i])   //放入栈
			{
				s.push(i);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

代码解释

1. 输入处理：读取天际线的宽度和高度数据。
2. 栈初始化：初始化栈并在高度数组的首尾添加0。
3. 遍历高度数据：
   • 使用单调栈维护高度序列，处理高度下降的情况。
   • 增加建筑物计数，并确保栈中高度的单调性。
4. 输出结果：打印最少建筑物数量。

这种方法确保了高效和正确的计算，适用于题目给定的数据规模。