Largest Empty Rectangle

Largest Empty Rectangle

問題:一張紙上有許多點,請在紙上畫出不包含任何點的矩形,且面積最大者。

此問題有兩種版本,一種是二維座標系統,另一種是棋盤座標系統(一個點為一個格子),我們主要介紹後者。

在介紹Largest Empty Rectangle之前,我們會先介紹一個較簡單的問題Largest Empty Interval。

Largest Empty Interval

Largest Empty Interval

問題:求出最長的那段空白處。

這個問題是Maximum Subarray的精簡版本,只要令數列裡的數字只有一跟負無限大即可。

不過這裡寫個跟先前不太一樣的程式碼。這支程式碼用了一個length陣列,紀錄每一個步驟當中所算出的目前最長長度。

為了讓程式碼更漂亮,這裡將map[]的位置都往右移動一格,並且預先將length都初始化為0。

要求最長的那一段的話就這麼寫。

大家現在應該能體會到這種Divide and Conquer、Dynamic Programming的方式和過程吧。

Largest Empty Rectangle之一

一些簡單的想法

最簡單的方法就是用窮舉法。矩形共有四個頂點,只要窮舉所有可能的頂點位置,就可以找出答案來。紙的長寬為H和W的話,共有H*W個位置可以放上頂點;要窮舉所有矩形,時間複雜度就是O((H*W)^4)。另外還要確定矩形內部有沒有包含點,時間複雜度就變成了O((H*W)^5)

要確定一個矩形的大小和位置,其實只要對角線的兩個頂點就夠了;要窮舉所有矩形,時間複雜度是O((H*W)^2)。確定矩形內部有沒有包含點,就是O((H^W)^3)。

要確定一個矩形的大小和位置,也可以利用矩形左上角的頂點、長、寬;要窮舉所有矩形,時間複雜度是O((H*W)^2)。確定矩形內部有沒有包含點,就是O((H^W)^3)。

談了一堆簡單的做法後,接著來試試Dynamic Programming吧!

Dynamic Programming

因為原來的紙張又大又複雜,計算面積非常麻煩,所以我們可以試著把紙張切成小塊小塊,逐一處理。這裡將紙張切成橫條狀(這個想法跟積分運算的道理是相同的),並套用上一篇文章所提到的Largest Empty Interval來計算面積;接著將所有橫條合併起來,便能求出總面積。

將紙張切成橫條狀,此即Divide;每個橫條用Largest Empty Interval來計算面積,此即Conquer;將所有橫條合併,此即Merge。接著來看看要怎麼找出Largest Empty Rectangle吧!

演算法

首先將紙張切成橫條狀,針對每一橫條,找出其中每個點往左可延伸的長度,即是在尋找Largest Empty Interval。

對紙張上的每個位置,都嘗試作為矩形右下角的頂點位置(窮舉所有矩形右下角的位置)。固定矩形右下角的頂點後,觀察該處以上的每個橫條(窮舉所有矩形高度),往左可延伸的長度,便可以求得最大矩形面積。

程式碼

為了讓邊界計算不會溢位,於是將紙張的外面多圍一圈。這是實作二維地圖時很常用的方法。

程式碼

先設計出計算一個橫條的程式碼──計算Largest Empty Interval,運用了DP。(這段程式碼在計算width時,每一格都會覆蓋掉而不受舊值影響,故重算時不必重新初始化。)

補足程式碼,計算所有橫條。

程式碼

對紙張上的每個位置,都嘗試作為矩形右下角的頂點位置。固定矩形右下角的頂點後,觀察該處以上的每個橫條,往左可延伸的長度,便可以求得最大矩形面積。

先設計出計算一個位置的程式碼。

判斷矩形太窄的情形。

補足程式碼,窮舉紙張上所有位置。

時間複雜度

首先用了一點DP的技術計算每個橫條的Largest Empty Interval,接著窮舉矩形的右下角頂點位置,又窮舉了矩形的各種高度,以DP的精神快速的算出最大矩形面積──時間複雜度是O((H*W)*H)。

另外,計算的方向是可以改變的。可以改為切直條、窮舉矩形右上角頂點,道理都一樣。

有好多好多類似的題目。有一些我也忘了題號。

UVa 108 836 10074 10502 10667

Largest Empty Rectangle之二

更快的方式

前面介紹的方法用了很多窮舉,也重複計算了很多地方。所以,還可以更快。

這個方法是窮舉紙張上每一個位置,每個位置都去計算以該點為長方形底部,往上延伸到底後,再往左右延伸到底的面積。

如果窮舉一個橫條上的所有位置,便可以得到以該橫條為長方形底部的Largest Empty Rectangle。

所以,只要窮舉紙張上每個位置,就可以算出Largest Empty Rectangle了。

討論

之前只將長方形往左延伸,故要窮舉所有高度。現在改為同時往左右延伸,由於這種延伸方式可得到最大的矩形,便不必窮舉所有高度。

Largest Empty Rectangle的面積

計算過程滿繁複的,不過大抵上和上一篇的方式差不多。我有點懶的說明,所以直接給程式碼吧(懶散是不好的行為,請勿模仿)。時間複雜度是O(H*W)。

Largest Empty Rectangle的位置

另外還要紀錄長方形往上、往左、往右可延伸的位置,還要紀錄產生最大值的位置。補一補程式碼即可。

Largest Empty Square

Largest Empty Square

跟Largest Empty Rectangle類似,只是改為找正方形而已。這裡介紹O(H*W)的方法,recurrence為:

area(i, j) = min( area(i-1, j), area(i, j-1), area(i-1, j-1) ) + 1

Uva 10908

Longest Plateau

Longest Plateau

問題:在一個排序過的數列中,相同的數字會連續出現。找出連續最多次的次數。一串連續相同的數字稱作一個plateau,而這個問題也就是要找出最長的plateau。

這個問題跟Longest Empty Interval有點像,不過這個問題卻有一個精妙的解法。請看程式碼。

這又讓我們多了一種思考問題的方式。謹此。