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

Question

我在 geeksforgeeks 上找到了这段代码，它可以工作。但我有一些疑问。在函数 calculateSpan() 的下一行中，while (!st.empty() && price[st.top()] < price[i]) .. 我们想将数组中第 i 个元素的值与堆栈顶部的元素进行比较，但是 st.top()给出栈顶元素的“值”，而不是栈顶的“索引”值，那么为什么行 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

在堆栈中 st在函数中定义 calculateSpan()我们正在插入日期索引 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 上元素的“值”本身就是数组 price 的“索引”值! 有道理吗？

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);

希望对您有所帮助!