一个简单向量的奇怪索引问题
strange index issue for a simple vector
我有一个数组,例如 {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());
......
正如评论中指出的那样,
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);
}
作为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
我有一个数组,例如 {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());
......
正如评论中指出的那样,
auto i=(prices.size()-1)
,i
is deduced to be unsigned value, and the conditioni >= 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);
}
作为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