我感觉我的思维真的和上学时不一样了，现在这些题目都能不看任何东西做出来，但是做法每一道都和网上的不一样
网上的解法：http://blog.sina.com.cn/s/blog_6cf509db0100swrb.html
网上的思路：找出以当前点位最低点能左右延伸的最长距离,也就是找出最左最右的下标，最后的 ans = max（s[i]*(r[i]-l[i]+1)) (1<=i<=n）!
我的思路：输入每个值，都检查这个新的点是否比当前最高的矩形低。如果比最高的矩形低，则算出最高的矩形面积，并删掉最高的矩形，重复此过程直到干掉所有过高的矩形，然后把当前的点作为矩形的起始位置放入链表。 链表是有序的。
分析时间复杂度，我的算法和网上时间复杂度同一个级数，但是我的算法循环个数更少，比网上算法更快一点点。我的算法124ms，网上171ms
#include <stdio.h>#include <stdlib.h>#include <string.h>#define SIZE 100010typedef struct { int high; int next;}dp_struct;dp_struct dp[SIZE+1];int head;int main(){ int n,i,temp; __int64 max,temp_max; int hi; dp[100010].high = 0; dp[100010].next = 0; while(1) { head = SIZE; max = 0; scanf("%d", &n); if(n == 0) break; for(i = 0; i < n; i++) { temp = i; scanf("%d", &hi); while(head != SIZE && dp[head].high > hi) { temp_max = (__int64)dp[head].high *( i - head); if(temp_max > max) max = temp_max; temp = head; head = dp[head].next; } if(dp[head].high == hi) { ; } else { dp[temp].high = hi; dp[temp].next = head; head = temp; } } while(head != SIZE) { temp_max = (__int64)dp[head].high *( n - head); if(temp_max > max) max = temp_max; head = dp[head].next; } printf("%I64d\n", max); } return 0;}
