其實(shí)并不是很難的一道題，但是思路錯(cuò)了就很容易被某些測(cè)試數(shù)據(jù)整崩，而且還看不到測(cè)試數(shù)據(jù)是什么就更讓人崩潰了……

這是我們期中考試的一道題，當(dāng)時(shí)被case28卡住time out了，因?yàn)槭莟ime out，所以也看不了測(cè)試數(shù)據(jù)。

我最開始的代碼是長這個(gè)樣子的：

其實(shí)這個(gè)也是前幾個(gè)case檢查出一些錯(cuò)誤，改過一兩次的結(jié)果。

它的大概思路是：每一根柱子都往后找最多能延長幾根，但是這樣不能找全，因?yàn)檫@根可能在最大矩形的中間位置。其實(shí)這個(gè)時(shí)候很好的一個(gè)思路已經(jīng)呼之欲出了，但我當(dāng)時(shí)沒有意識(shí)到：最大矩形的高度一定是他所包含的最低柱子的高度，所以對(duì)于每根柱子，我們分別向前、向后延長，找到最大面積，最后取最大：這便是最大面積了。

但我當(dāng)時(shí)腦子沒有轉(zhuǎn)過來，于是我的思路就是把每根柱子的長度都遍歷一遍，每個(gè)長度都試一下最多能往右走多少。

這個(gè)思路雖然有點(diǎn)蠢，但畢竟可行，于是跑了28個(gè)case（第一個(gè)case是case 0），可是在case 28，它被卡住，time out了。

我當(dāng)時(shí)只當(dāng)是他給了一些很大的數(shù)，而我的算法有問題比較慢，所以我又轉(zhuǎn)換思路換了種算法寫（但其實(shí)新算法也不會(huì)快）。

新的算法是這樣的：

這里的大概想法是這樣的：先遍歷一遍找到最高柱子，然后從最高高度開始“切”，切出一些矩形，找其中最大的。

不過嘛……這個(gè)其實(shí)并沒有快多少，并且在提交后毫無懸念地停在了case 28:time out.

后來我就沒有再管它了。而昨天計(jì)概老師開放了“期中考試復(fù)盤”的練習(xí)，我便又有了看看到底是什么卡住了我的想法。

我想了想，還是用了switch print大法。一個(gè)一個(gè)答案打表，最后用了200多行switch（只看n和前兩個(gè)柱子就能區(qū)分了，所以是三層switch），整出了一個(gè)O(1)的算法（霧

（貼上代碼供大家一樂

當(dāng)我看到case28的內(nèi)容時(shí)，我有點(diǎn)崩潰。

測(cè)試數(shù)據(jù)是這樣的：

9

0 0 0 0 0 0 0 0?2147483648

問題得到解決了：不管是哪種算法，都無一例外地會(huì)在這里卡死：因?yàn)楸闅v的輪數(shù)直接取決于最高柱子的高度。兩種算法都會(huì)在這里跑2^31次，這誰頂?shù)米“　?/p>

其實(shí)我當(dāng)時(shí)考完也有過這種猜測(cè)，并且也想到一些解決方法。

其中一個(gè)就是：如果他存心為難我，放幾個(gè)特別高的柱子，那我可以維護(hù)一個(gè)比較小的數(shù)組，里面存放那幾個(gè)比較高的柱子，先把這幾個(gè)走一遍，接著再從這里最低的柱子開始往下切。

既然有方法，那我直接用就好了吧。我偷了個(gè)懶，覺得可能只有這一個(gè)麻煩的東西，于是沒有維護(hù)數(shù)組，而是單挑了一個(gè)最大的數(shù)出來。當(dāng)然，其實(shí)這應(yīng)該叫維護(hù)了一個(gè)2長的數(shù)組，因?yàn)橐獜淖畹偷闹釉匍_始往下切，如果只有一個(gè)最大是沒有意義的，還應(yīng)該有第二大，確定開始切的位置。

代碼就是這樣了：

這個(gè)代碼非常堅(jiān)挺，一直活了89個(gè)case，但在case 89它倒下了。它也超時(shí)了。我估測(cè)是這里面不止一個(gè)高度離譜的柱子。這沒辦法了，萬一也不止兩個(gè)呢？還要寫幾個(gè)max呢？

辦法自然是有的，比如拷貝一份數(shù)組，然后對(duì)這個(gè)進(jìn)行局部冒泡排序，找?guī)讉€(gè)比較大的，維護(hù)這個(gè)數(shù)組，然后按著那個(gè)方法……

可是有沒有一種可能，一開始思路就錯(cuò)了？

我開始反思，而后意識(shí)到：確實(shí)如此。

對(duì)于一根柱子，它不止可以向左，也可以向右，而對(duì)每根柱子都如此操作，自然可以獲得最大面積。我們甚至也可以給出嚴(yán)謹(jǐn)?shù)淖C明，用反證法：假如最大面積不是由任何一根柱子向左右延伸而得到，那么我們可以找到這個(gè)面積中最矮的柱子，它的高度一定大于矩形高度。將該柱子向左右延伸得到新矩形，兩矩形寬度一定相等，而新矩形高于原矩形，則新矩形面積大于原矩形，矛盾。證畢。

（好吧這其實(shí)就是一堆廢話

于是我們得到了一些很簡單的代碼：

這個(gè)自然還是有一些優(yōu)化空間的，不過其實(shí)沒必要再優(yōu)化了。代碼的時(shí)間復(fù)雜度是，與給出的數(shù)據(jù)無關(guān)了（當(dāng)然也會(huì)有關(guān)系，不過不會(huì)像前面的代碼那樣被某些數(shù)據(jù)卡死了）。

總之就是：王小明，你糊涂?。。。。。。。?/p>

怎么會(huì)想到之前那些鬼畜的想法的?。。。。?/p>