[单调栈] 统计点数
题目描述
给你平面上 N N N 个点，求有多少个点右上方没有其他点（包括正上方和正右方）。
输入格式
一行
N
N
N，表示点的数量。
接下来
N
N
N 行，每行两个数
x
,
y
x, y
x,y，表示一个点的坐标。
输出格式
一行表示答案。
样例
样例输入1：
4
1 0
0 1
1 1
0 0
样例输出1：
1
数据范围
对于
50
%
50\%
50% 的数据，
N
≤
1000
N \le 1000
N≤1000
对于
100
%
100\%
100% 的数据，
N
≤
100000
N \le 100000
N≤100000，
x
x
x 和
y
y
y 的绝对值在 int 范围，不会出现两个坐标相同的点。
题解
假设选了
(
x
,
y
)
(x, y)
(x,y)，则下一次选的点的坐标要么
x
x
x 大于当前的
x
x
x，要么
y
y
y 大于当前的
y
y
y 且
x
x
x 小于当前的
x
x
x。
将
x
x
x 坐标从大到小排序，这样只用考虑第
2
2
2 种情况了。
将每个点依次遍历，加入单调栈进行维护
y
y
y，最后输出单调栈的长度即可。
代码：
stack<int> st;
pair<int, int> a[1000010];
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; ++ i){
scanf("%d %d", &a[i].first, &a[i].second);
}
//排序
sort(a + 1, a + n + 1);
//维护单调栈
for(int i = 1; i <= n; ++ i){
while(!st.empty() && st.top() <= a[i].second){
st.pop();
}
st.push(a[i].second);
}
printf("%d", st.size());
return 0;
}