LC的课后辅导 QDU

LC的课后辅导 QDU

此题暴力可过(O(n^2)) 亦可用栈优化(O(n)) 即通过栈保存矩形编号 找出每个矩形左右可到达的最远边界

例如从左至右遍历 遍历至哪个矩形 该矩形的左边界即可得

假设遍历至h[i]矩形 若栈顶元素stack[top]==p即为h[p]矩形的编号

若h[p]大于h[i] 则弹出栈顶元素而看栈中下一个元素 直至某个矩形h[q]小于h[i] 则确定为h[i]矩形的边界(具体原因要思考)

#include int main(){ int h[101],ans1[101],ans2[101],stack[101]; int n,i,top,sum,max; while(scanf("%d",&n)!=EOF) { if(n==0) break; for(i=1;i<=n;i++) { scanf("%d",h+i); } top=0; for(i=1;i<=n;i++) { while(top!=0&&h[stack[top]]>=h[i]) top--; if(top==0) { ans1[i]=1; } else { ans1[i]=stack[top]+1; } top++; stack[top]=i; } top=0; for(i=n;i>=1;i--) { while(top!=0&&h[stack[top]]>=h[i]) top--; if(top==0) { ans2[i]=n; } else { ans2[i]=stack[top]-1; } top++; stack[top]=i; } max=0; for(i=1;i<=n;i++) { sum=h[i]*(ans2[i]-ans1[i]+1); if(sum>max) max=sum; } printf("%d\n",max); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。