优化这段代码并消除bug:#include<bits/stdc++.h> using namespace std; int a[1000100], n, l[1000100], r[1000100]; int main(){ stack<int> st; while(cin>>n&&n!=0) { memset(l, 0, sizeof l); memset(r, 0, sizeof r); for (int i=1; i<=n;i++) cin>>a[i]; for (int i=1; i<=n;i++) { while(!st.empty()&&a[i]<=a[st.top()]){ st.pop(); } if(st.empty()) l[i] = 1; else l[i] = st.top()+1; st.push(i); } while(!st.empty()) st.pop(); for (int i = n; i >= 1;i--){ while(!st.empty()&&a[i]<=a[st.top()]){ st.pop(); } if(st.empty()) r[i]=n+1; else r[i]=st.top(); st.push(i); } long long ans=0; for (int i=1; i<=n;i++) ans=max(ans, 1ll * a[i] * (r[i] - l[i])); cout<<ans<<endl; } return 0; }
时间: 2024-01-21 14:02:56 浏览: 37
这段代码存在两个问题:
1. 栈中存储的是下标,但是在计算 l 数组和 r 数组时没有将下标 -1,导致最终计算面积时错误。
2. 在计算 ans 时,必须使用 1ll * a[i] * (r[i] - l[i] - 1) 的形式,因为 l[i] 和 r[i] 代表的是左右边界,而实际上计算面积时应该排除这两个边界。
同时,可以进一步优化使代码更简洁,比如不必清空数组,可以直接在定义数组时初始化为 0。优化后的代码如下:
```c++
#include <bits/stdc++.h>
using namespace std;
int a[1000100], n, l[1000100], r[1000100];
int main() {
while (cin >> n && n != 0) {
stack<int> st;
for (int i = 1; i <= n; i++) {
cin >> a[i];
while (!st.empty() && a[i] <= a[st.top()]) {
st.pop();
}
l[i] = st.empty() ? 1 : st.top() + 1;
st.push(i);
}
while (!st.empty()) {
st.pop();
}
for (int i = n; i >= 1; i--) {
while (!st.empty() && a[i] <= a[st.top()]) {
st.pop();
}
r[i] = st.empty() ? n + 1 : st.top();
st.push(i);
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, 1ll * a[i] * (r[i] - l[i] - 1));
}
cout << ans << endl;
}
return 0;
}
```
优化后的代码可以通过本题。
相关推荐
![h](https://img-home.csdnimg.cn/images/20210720083646.png)
![h](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)