本文主要是介绍单调栈之Bad Hair Day题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:
Some of Farmer John's N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows' heads.
Each cow i has a specified height hi (1 ≤ hi ≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow i can see the tops of the heads of cows in front of her (namely cows i+1, i+2, and so on), for as long as these cows are strictly shorter than cow i.
Consider this example:
=
= =
= - = Cows facing right -->
= = =
= - = = =
= = = = = =
1 2 3 4 5 6
Cow#1 can see the hairstyle of cows #2, 3, 4
Cow#2 can see no cow's hairstyle
Cow#3 can see the hairstyle of cow #4
Cow#4 can see no cow's hairstyle
Cow#5 can see the hairstyle of cow 6
Cow#6 can see no cows at all!Let ci denote the number of cows whose hairstyle is visible from cow i; please compute the sum of c1 through cN.For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.
Input
Line 1: The number of cows, N.
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i.Output
Line 1: A single integer that is the sum of c 1 through cN.
Sample Input
6
10
3
7
4
12
2
Sample Output5
题意:每个奶牛都有一个高度,奶牛们排成一排,且面朝右方向,问每个奶牛能看到奶牛数目的和是多少
- 解题思路:
可以使用单调栈来解决此题。从每只奶牛能看到多少脑袋,转换为它能被多少人看到,即每只奶牛后方(注意:奶牛是面朝右边的)有多少比它高的存在(存在遮挡现象,如果某只奶牛后方的一只或者多只奶牛比它矮,那么这一只或者多只就需要出栈)
该题源自于北大OJ:3250 -- Bad Hair Day
具体的解题思路如下,以该题的样例为例:10 3 7 4 12 2
1、将第1个元素入栈
2、将第2个元素与栈顶元素进行比较
如果第2个元素大于栈顶元素就将栈顶元素出栈,代表此时第1个元素看不到第2个元素。
如果第2个元素小于等于栈顶元素。此时计数变量+1,代表第1个元素可以看到第2个元素,并且将第2个元素入栈。 将第3个元素与栈顶元素进行比较
3、将第3个元素与栈顶元素进行比较
如果第3个元素大于栈顶元素就将栈顶元素出栈,代表此时第2个元素看不到第3个元素,出栈后,让第3个元素再次与栈顶元素比较,直到栈空或者第3个元素小于等于栈顶元素。
如果第3个元素小于等于栈顶元素。此时计数变量+栈中的元素个数,代表栈中的每个元素都可以看到第3个元素,之后以此类推,如下图演示
AC代码:
注意:这里要注意数据的范围,计数变量sum可能会超过int范围,需要定义为long long类型
#include<iostream> #include<stack> using namespace std; int a[100000]; long long sum=0; stack<int> s; //6 10 3 7 4 12 2 void nextLesser(int a[],int n) {for(int i=1;i<=n;i++){//单调栈,>= while(!s.empty()&&s.top()<=a[i]){s.pop(); }sum+=s.size();s.push(a[i]); } } int main() {int n;scanf("%d",&n); for(int i=1;i<=n;i++){scanf("%d",&a[i]);}nextLesser(a,n);cout<<sum;return 0; }
总结:
不断练习,不断总结。
前路漫漫,当克己,当慎独。
欢迎广大朋友,加入算法群进行讨论和分享资料
这篇关于单调栈之Bad Hair Day题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!