这个算法的复杂度是多少
What is the complexity of this algorithm
该算法以一个整数向量作为输入，首先存储最大值，让我们保持它在数组中的位置 p，然后我们将最大元素存储在 [p, n[ 范围内，依此类推。
// input v[0]...v[n-1] is a vector of integers already filled.
// output : stack s
stack<int> s;
for(auto x: v){
while(!s.empty() && x > s.top()) s.pop();
s.push(x);
}
我想不出最坏的情况，但算法似乎是线性的，因为 while() 工作得越多，堆栈大小就会减少得越多，从而使未来的工作变得非常便宜。
最坏情况
你的程序是将最大值放在栈底。您将执行 N 次 push() 操作。最坏的情况下，你会 pop() N-1 次。 （因为你不能弹出超过 N-1 次，否则你将得到空堆栈，这违背了程序的目的）。
最佳情况
最好的情况是向量 V 的第一个元素的最大值。您仍然执行 N push() 操作并且永远不会执行任何 pop() 操作。
所以在一天结束时，无论向量 V 中的任何数据如何，它都会以线性时间执行。
该算法以一个整数向量作为输入，首先存储最大值，让我们保持它在数组中的位置 p，然后我们将最大元素存储在 [p, n[ 范围内，依此类推。
// input v[0]...v[n-1] is a vector of integers already filled.
// output : stack s
stack<int> s;
for(auto x: v){
while(!s.empty() && x > s.top()) s.pop();
s.push(x);
}
我想不出最坏的情况，但算法似乎是线性的，因为 while() 工作得越多，堆栈大小就会减少得越多，从而使未来的工作变得非常便宜。
最坏情况
你的程序是将最大值放在栈底。您将执行 N 次 push() 操作。最坏的情况下，你会 pop() N-1 次。 （因为你不能弹出超过 N-1 次，否则你将得到空堆栈，这违背了程序的目的）。
最佳情况
最好的情况是向量 V 的第一个元素的最大值。您仍然执行 N push() 操作并且永远不会执行任何 pop() 操作。
所以在一天结束时，无论向量 V 中的任何数据如何，它都会以线性时间执行。