[基础算法1 ] 朋友的数量
题目描述
题目描述：
很多幼儿园的小朋友到一起参加市里的联欢晚会，排成了一个长队，小朋友们排队有点无聊了，东张西望。如果两个小朋友之间的人都不比他们两个高，他们就可以互相看到，于是他们就成为了一对好朋友。当然如果两个小朋友之间没有其它小朋友，则他们也会是一对好朋友。现在，请你算一下一共有几对好朋友。
两个小朋友甲和乙，(甲, 乙)和(乙, 甲)只能算一对好朋友。
输入格式：
第一行n，表示小朋友个数
第二行n个正整数，表示小朋友的高度
输出格式：
一个数字，表示好朋友的对数
样例输入 复制
4 5 1 3 4
样例输出 复制
5
提示
样例1说明：(5, 1)、(5, 3)、(5, 4)、(1, 3)、(3, 4)，一共5对。
数据范围：
20%：n<=1000，高度不会重复
40%：n<=10,000，高度有重复
100%：n<=500,000，高度有重复
程序
#include <iostream>#include <algorithm>#include <stack>using namespace std;stack<int> st;int a[500005];int main(){ int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; int ans(0); for (int i = 1; i <= n; i++) { int t(1); while (!st.empty() && a[st.top()] <= a[i]) { if (a[st.top()] == a[i]) t++; ans++; st.pop(); } if (!st.empty()) ans++; while (t--) st.push(i); } cout << ans; return 0;}