对于一些未知的测试用例,我得到了分割错误,但我无法解决它。大多数情况下都是这样。我只想知道在这种情况下,我得到分割错误。该代码是为问题的最大矩形面积在直方图中编写的。您可以在这里检查这个问题:https://practice.geeksforgeeks.org/problems/maximum-rectangular-area-in-a-histogram-1587115620/1#
以下是代码:
long long getMaxArea(long long arr[], int n)
{
int nsl[n];
int nsr[n];
stack<int>s;
// nsl
for(int i=0;i<n;i++)
{
if(i==0)
{
nsl[i]=-1;
s.push(i);
}
else{
while(!s.empty())
{
if(arr[s.top()]<arr[i])
break;
s.pop();
}
if(s.empty())
nsl[i]=-1;
else
nsl[i]=s.top();
s.push(i);
}
}
stack<int>st;
// nsr
for(int i=n-1;i>=0;i--)
{
if(i==n-1)
{
nsr[i]=n;
st.push(i);
}
else{
while(!st.empty())
{
if(arr[st.top()]<arr[i])
break;
st.pop();
}
if(st.empty())
nsr[i]=n;
else
nsr[i]=st.top();
st.push(i);
}
}
long long ans=0;
for(int i=0;i<n;i++)
ans=max(ans,arr[i]*(nsr[i]-nsl[i]-1));
return ans;
}发布于 2021-12-22 06:29:52
用矢量代替阵列解决了问题。我只是对数组使用了糟糕的c++语法,因此使用向量解决了它。
https://stackoverflow.com/questions/70441031
复制相似问题