递减栈维护-(POJ3250)Bad Hair Day(发型糟糕的一天)

妖狐艹你老母 2022-05-17 02:54 123阅读 0赞

*  # 递减栈维护-(POJ3250)Bad Hair Day(发型糟糕的一天) #

--------------------

*  ## 题目链接：[发型糟糕的一天][Link 1] ##
 *  ## 思路一： ##

**从前往后栈**，按顺序进入一个身高值，**将栈中 小于(或等于)该身高的数据弹出，栈中剩下的元素对应的牛都能看见该身高的牛。算出num后入栈该身高**

栗子：10 3 7 4 12 2

①**Height\_List：10**  入栈首身高

②3<10，不弹出，**num=0+1（当前栈中元素数）**，3入栈后 **Height\_List：10 3**

③7 > 3（3 弹出） 7<10（10保留），栈中剩 10 ，num=1+1，7入栈后 **Height\_List：10 7**

④4 < 7，没有弹出，栈中10 7都能看到4，num=2+2 ，4入栈后 **Height\_List：10 7 4**

⑤12大于栈中全部元素，表示栈中所有元素看不到12，全部出栈，num不变，12入栈后 **Height\_List：12**

⑥2 < 12，没有弹出，12能看到2，num=4+1

**最后结果num=5**

**My Puzzle Before：**最初我在想为什么弹出一个元素对整个结果没有影响，首先弹出元素是因为它右边相邻牛比它高（**看不到它的头发并且挡住了该牛的视线**），“挡住”这个关键字很重要，这就是说***该牛已经看不到后面的其他牛的头发啦***，而思路一是按顺序比较身高，**统计每头牛前面能看到它头发的牛数**，既然该牛望不到后面，那么把它出栈对整个结果没有影响。

*  ## 代码一： ##

#include<iostream>
    #include<stack>
    using namespace std;
    
    
    int main()
    {
    	long long sum = 0, OX_Num, Height;
    	stack<long long> Height_List;
    	cin >> OX_Num;
    
    	cin >> Height;
    
    	Height_List.push(Height);
    	OX_Num--;
    
    	while (OX_Num--)
    	{
    		cin >> Height;
    		while (!Height_List.empty() && Height >= Height_List.top())   //弹出栈顶身高小于（等于）输入身高的元素
    			Height_List.pop();
    		sum += Height_List.size();  //size表示能看到即将入栈的牛的数量
    		Height_List.push(Height);	//该牛的身高入栈
    	}
    
    	cout << sum << endl;
    	return 0;
    
    }

*  ## 思路二： ##

**从后往前栈**，只不过栈的是坐标，先入栈一个相对无穷大数，按输入的后序取身高，将栈中 **小于该身高**的身高相应坐标弹出，弹出数代表该身高牛能看到后面头发的牛数。

栗子：10 3 7 4 12 2 max(下标6定义个相对无穷大数)

①**Less\_stack：6 5**

②12 > 2 （弹出4），num=0+1 ，入栈12对应下标，**Less\_stack：6 4**

③4 < 12 （不弹出），num不变，入栈4对应下标，**Less\_stack：6 4 3**

④7 > 4（弹出3），num=1+(4-2-1)，入栈3对应下标，**Less\_stack：6 4 2**

⑤3 < 7（不弹出），num不变，入栈3对应下标，**Less\_stack：6 4 2 1**

⑥10 > 3 , 7（弹出1 2），num=2+(4-0-1）=5

**最后结果num=5**

**My Puzzle Before：**我还是在纠结为什么元素能出栈，这里出栈的原因是被前面的牛看见，而且主要到计算某头牛看见后面牛头发的数量是通过出栈后**比较栈顶（存下标）和当前牛坐标的**，举个栗子 10 9 8 7 6 5 4，如果是这个序列，那么每入一头牛之前都会把栈弹空，所以每次栈顶存的下标值都是7，这提示我，如果一只牛出栈，前面某一只牛（不是相邻）看到了该牛，势必会弹出两头牛之间的牛，**所以计算下标是算到弹出的这头牛后面的对应下标**，所以弹出没有影响。

*  ## 代码二： ##

#include<iostream>
    #include<stack>	
    using namespace std;
    #define MAX_Length 80001
    
    int main()
    {
    	int OX_Num;
    	long long OX_List[MAX_Length], sum = 0;
    	stack<long long> Less_stack;
    
    	cin >> OX_Num;
    	for (int i = 0; i < OX_Num; i++)
    		cin >> OX_List[i];
    
    	Less_stack.push(OX_Num);
    
    	OX_List[OX_Num] = (long long)10000000001;
    
    	for (int i = OX_Num - 1; i >= 0; i--)
    	{
    		while (OX_List[i] > OX_List[Less_stack.top()])		//弹出栈中所有身高小于OX_List[i]的元素
    			Less_stack.pop();
    		sum += Less_stack.top() - i - 1;   //计算总弹出数，弹出数表示OX_List[i]能看到的牛数
    		Less_stack.push(i);		//下标入栈
    	}
    
    	cout << sum << endl;
    
    	return 0;
    }

[Link 1]: http://dsalgo.openjudge.cn/stackqueue/9/