无法理解使用 C++ STL 的 Stock 跨度的线性时间方法

Question

我在 geeksforgeeks 上找到了这个代码并且它有效。但是我有几个 doubts.Inthe 函数 calculateSpan()，在下一行中，while (!st.empty() && price[st.top()] < price[i])..我们想将数组中第 i 个元素的值与堆栈顶部的元素进行比较，但是 st.top() 给出栈顶元素的 "value"，而不是栈顶元素的 "index" 值，那么为什么行 price[st.top()] 仍然有效。同样在 calculateSpan() 函数的最后一行，st.push(i) 用于将当前元素推入堆栈，如前所述，但这不应该将 'i' 的值推入堆栈顶部。这段代码是如何工作的？我已经发布了完整的代码。提前致谢。 `

// a linear time solution for stock span problem
#include <iostream>
#include <stack>
using namespace std;


void calculateSpan(int price[], int n, int S[])
{
// Create a stack and push index of first element to it
    stack<int> st;
    st.push(0);

// Span value of first element is always 1
   S[0] = 1;

 // Calculate span values for rest of the elements
  for (int i = 1; i < n; i++)
  {
    // Pop elements from stack while stack is not empty and top of
    // stack is smaller than price[i]
      while (!st.empty() && price[st.top()] < price[i])
       st.pop();

   // If stack becomes empty, then price[i] is greater than all elements
   // on left of it, i.e., price[0], price[1],..price[i-1].  Else price[i]
   // is greater than elements after top of stack

     S[i] = (st.empty())? (i + 1) : (i - st.top());

  // Push this element to stack
    st.push(i);
  }
}

// A utility function to print elements of array
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
         cout << arr[i] << " ";
}

// Driver program to test above function
 int main()
 {
    int price[] = {1, 4, 50, 90, 12, 80};
    int n = sizeof(price)/sizeof(price[0]);
    int S[n];

  // Fill the span values in array S[]
   calculateSpan(price, n, S);

 // print the calculated span values
    printArray(S, n);

    return 0;
}

Answer 1

在函数 calculateSpan() 定义的 Stack st 中，我们插入天数 0,1,2,3,4,5 的索引，因此当我们看到 st.top() 给出索引时数组的 price[] 也。

如你所说：

but st.top() gives the "value" of the element on stack top, not the "index" value of stack top

这里stack top上元素的"value"本身就是数组price的"index"值！ 有道理吗？

while (!st.empty() && price[st.top()] < price[i])
   st.pop();

所以，在上面的代码中price[st.top()] < price[i]表示price[day-index] < price[selected day]。请记住，我们将 day-index 压入堆栈。

而且由于我们将天索引压入堆栈 st 所以，我想最后几行现在也有意义

st.pop(i) // i=0,1,2,3,4,5

注意：永远不要忽略写在代码主体上的注释！例如，我猜你错过了那个评论！

// Create a stack and push index of first element to it
stack<int> st;
st.push(0);

希望对您有所帮助！

Answer 2

堆栈 st 是 int 类型元素的堆栈，因此 st.top() 给出一个 int，显然应该由 st.push( int ) 插入。这里的堆栈包含数组索引（天）。 st.top() 给出最后一个推送到 st 的数组索引，st.pop() 删除最后一个推送到 st.

不确定上述实现是否考虑了 price[ i ] > price[i-2] 且 price[i-1] < price[i] 且 < price[i - 2] 的情况。

另一种没有栈数据结构的实现：

S[0] = 1;
  for (int i = 1; i < n; i++)
  {

      if ( price[ i ] >= price[ i - 1 ] )
      {
          S[ i ] = S[ i - 1 ] + 1;
          for ( int j = i - S[i]; price[i] >= price[j] && j >= 0 ; j-- ) //look for prices less than price[i] but greater than price[i-1]
              S[ i ] += 1;
      }
      else
          S[ i ] = 1;
  }

复杂度：

最好的情况是数组排序 T(n) = n 次。

最坏的情况是 price[i] 大于所有之前的价格并且 price[i-1] 小于或等于它之前的所有价格：

int 价格[] = {0, 1, 0, 2, 0, 3,0,4,0,5,0,6,0,7,0,8,0,9,0,10 ,0,11};// n=22

T(n)=1+2+1+4+1+6+1+8+1+10+1+12....+1+ 2 * (n/2)。

有n/2个循环形成公差为2 + n/2次的等差级数，其中只有1条指令（价格[i] <价格[i-1]的情况）。

T(n) 那么就是 n/2 + n/4 * [ ( 2*2 + 2 * ( (n/2) - 1 ) ] = n/2 + n/4 * ( 2 + n ) = n + [ (n^2) / 4 ]。这是当 n 为偶数时。当 n 为奇数时，它变为 1 + n/2 + [ (n^2) / 4 ]

无法理解使用 C++ STL 的 Stock 跨度的线性时间方法

Can't understand linear time method for Stock span using C++ STL

c++

stl