一个简单向量的奇怪索引问题

Question

我有一个数组，例如 {7, 3, 1, 5, 2}。我想从一个索引开始获取最大值，所以结果应该像 {7, 5, 5, 5, 2}。我只是像下面这样使用 for 循环。它抛出奇怪的堆溢出问题。

    int maxProfit(vector<int>& prices) {
      vector<int> maxRight;
      int runningMax = 0;
      for(auto i=(prices.size()-1);i>=0;i--){
        if(runningMax < prices[i]){
          runningMax = prices[i];
        }
        maxRight.push_back(runningMax);
      }  
      maxRight.push_back(runningMax);
      std::reverse(maxRight.begin(), maxRight.end());
      ......

但是如果我改成下面的代码，它就可以工作了。下面的代码和上面的不一样吗？我只是将索引 i 的比较更改为 0 或 1。

    int maxProfit(vector<int>& prices) {
      vector<int> maxRight;
      int runningMax = 0;
      for(auto i=(prices.size()-1);i>=1;i--){
        if(runningMax < prices[i]){
          runningMax = prices[i];
        }
        maxRight.push_back(runningMax);
        
      }  
      if(runningMax < prices[0]){
        runningMax=prices[0];
      }
      std::reverse(maxRight.begin(), maxRight.end());
      ......

Answer 1

正如评论中指出的那样，

auto i=(prices.size()-1) , i is deduced to be unsigned value, and the condition i >= 0 is always true. You have accessing out of bounds of array.

不使用索引，而是使用迭代器，在本例中为 std::vector::reverse_iterator.

for(auto it = prices.rbegin(); it != prices.rend(); ++it)
{
    if(runningMax < *it)
    {
        runningMax = *it;
    }
    maxRight.push_back(runningMax);    
}

Answer 2

作为for循环中声明的变量i

for(auto i=(prices.size()-1);i>=0;i--){

具有无符号整数类型 std::vector<int>::size_type 然后你将得到一个无限循环，因为当 i 等于 0 时表达式 i-- 将产生一个非-负数。

另一个问题是，如果由于 for 循环声明部分的初始化而传递的向量为空，for 循环将再次调用未定义的行为

auto i=(prices.size()-1)

因为 prices.size()-1 在这种情况下产生正值。

在第二个函数实现中，您忘记为向量的第一个元素推送计算值 prices。你刚刚在循环后写了

  if(runningMax < prices[0]){
    runningMax=prices[0];
  }

这没有多大意义。 ` 您可以编写一个单独的函数，returns 所需的最高价格向量。

这是一个演示程序。

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

std::vector<int> max_prices( const std::vector<int> &prices )
{
    std::vector<int> maxRight;
    maxRight.reserve( prices.size() );
    
    for ( auto first = std::rbegin( prices), last = std::rend( prices ); 
          first != last; 
          ++first )
    {
        if ( maxRight.empty() )
        {
            maxRight.push_back( *first );
        }
        else 
        {
            maxRight.push_back( std::max( maxRight.back(), *first ) );
        }
    }         
    
    std::reverse( std::begin( maxRight ), std::end( maxRight ) );
    
    return maxRight;
}

int main() 
{
    std::vector<int> prices = { 7, 3, 1, 5, 2 };

    auto maxRight = max_prices( prices );
    
    for ( const auto &price : maxRight )
    {
        std::cout << price << ' ';
    }
    std::cout << '\n';
    
    return 0;
}

程序输出为

7 5 5 5 2

一个简单向量的奇怪索引问题

strange index issue for a simple vector

c++

for-loop

vector

max