发型糟糕的一天(简单的单调栈运用)

提供两种解法,比较类似
一种是从后向前维护单调递增栈;
另一种是从前向后维护单调递减栈.

描述
农夫John 的N(1 ≤ N ≤ 80,000)只奶牛中，有一些也许正在经历发型糟糕的一天。每只奶牛对自己乱糟糟的发型都有自知之明，农夫John想知道所有奶牛能看到其他奶牛头顶的数量之和。任意奶牛i身高记为 hi (1 ≤ hi ≤ 1,000,000,000)，所有奶牛面向东方（本题示意图的右面）依次站成一条线。因此，奶牛i能够看到在它前面的（奶牛i+1，i+2…）所有身高比它低的奶牛，直到被一头比它高的奶牛挡住考虑如下的例子：        =
=       =
=   -   =         Cows facing right ->
=   =   =
= - = = =
= = = = = =
1 2 3 4 5 6 
奶牛#1 可以看见奶牛#2, 3, 4的头顶奶牛#2 无法看到任何奶牛的头顶奶牛#3可以看见奶牛#4的头顶奶牛#4无法看到任何奶牛的头顶奶牛#5可以看见奶牛#6的头顶奶牛#6无法看到任何奶牛的头顶!用ci表示奶牛i能够看到头顶的奶牛个数；请计算c1 至cN的和。对于上面这个例子，其和为：3 + 0 + 1 + 0 + 1 + 0 = 5。输入
第1行：奶牛数N第2行至N+1行：第i+1行包含一个整数，表示奶牛i的高度输出
第1行：c1 至cN的累加和样例输入
6
10
3
7
4
12
2样例输出
5

/*解法1：
#include 
#include 
#include 
using namespace std;int N;
long long res, height[81000], num[81000];int main()
{cin>>N;stack s;for(int i=0;i"%lld",&height[i]);height[N] = 1000000001;s.push(N);for(int i=N-1;i>=0;i--){while(height[i] > height[s.top()])s.pop();num[i] = s.top()-i-1;res += num[i];s.push(i);}printf("%lld\n",res);return 0;
}
*//*
解法二：#include #include using namespace std;int main(){long long n,h,sum=0;cin >> n;stack<int>s;cin >> h;s.push(h); n -= 1;while (n--){cin >> h;while (!s.empty() && h >= s.top()){s.pop();}sum += s.size();s.push(h);}cout << sum << endl;return 0;}
*/

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！