1、&By 1看一個(gè)簡單問題求一串?dāng)?shù)的最長不降子序列的個(gè)數(shù)。如：1 3 6 2 7 5 8 9ans：6維護(hù)一個(gè)單調(diào)不減棧2例題：Largest Rectangle in a Histogram（POJ2559）給定一串長度為n(n = 100000)的序列hi(hi = 109)，可以畫出其直方圖，問其中面積最大的矩形是多大？如 n = 7, 序列為2 1 4 5 1 3 33思想樸素的做法，復(fù)雜度最壞為O（n2）對于一個(gè)數(shù)ai來說，如何找到向左和向右能擴(kuò) 展到的位置？ 兩種實(shí)現(xiàn)方法，模擬下 4核心代碼一：棧掃描（單調(diào)棧），復(fù)雜度接近O（n） long long ans = 0; int top

2、 = 0; listn = 0; stacktop = list0; idxtop+ = 0; for(int i=1;i listi) while(top 0 & stacktop-1 listi) long long tmp = (long long)(i - idxtop-1) * stacktop-1; if(tmp ans) ans = tmp; top-; stacktop+ = listi; else stacktop = listi; idxtop+ = i; printf(%lldn,ans);5核心代碼二：將高度從高到低排序，用并查集維護(hù)當(dāng)前集合的寬度（節(jié)點(diǎn)個(gè)數(shù)），取max

3、(當(dāng)前高度 * 寬度)為答案。復(fù)雜度為O(nlogn + na(n)hn + 1 = h0 = -1;for(i = 1; i = n; i+) li = ri = i;for(i = 1; i = hi) li = lli - 1;for(i = n; i = 1; i-)while (hri + 1 = hi) ri = rri + 1;6作業(yè)：POJ 2559 3494 2796 2082 （差不多一樣的） POJ 2452（思想難） 7例題：Second My Problem First（hdu 3706）Give you three integers n(1 = n = 107)，A and B(1 = A, B = 231-1)Define Si = Ai mod B and Ti = Min Sk | i-A = k = 1 . Calculate the product of Ti (1 = i = n) mod B.8核心代碼：long long tmp = 1,res = 1; int head = 0,rear = -1; for(int i=1;i= head & Qrear = tmp) rear-; Q+rear = tmp; idxrear = i; while(idxhead i - a) head+;