算法筆試模拟題精解之“最大矩形面積”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

https://developer.aliyun.com/coding

本文為大家介紹其中的 第46題：最大矩形面積 的題目解析，具體如下：

題目描述

題目等級：容易

知識點：數組

檢視題目：最大矩形面積

有n根木棍(4<=n<=1e5)，它們的長度分别為a1,a2,a3...an(1<=ai<=1e9)，現在請你從中挑選出4根木棍來組成一個矩形，問這個矩形的最大面積是多少?

輸入木棍數n和n個木棍長度

輸出能組成的矩陣的最大面積

示例1

輸入：

6

[1,1,2,2,3,3]

輸出：

解題思路

根據題意，想要組成面積最大的矩形，需要有最大的長與寬，并且組成長與寬的木棍都需要有2根，是以，隻要選擇最大的兩組木棍即可組成最大的矩形。

先對數組從大到小排序，編譯尋找最大的木棍，然後周遊數組。找到兩個連續的相同數字，記錄下這個位置，以這兩個數字組成矩形的兩條長。接下來從剛才記錄的位置接着往下找，再找出兩個連續的相同數字，以此組成矩形的兩條寬。将找出的矩形的長與寬相乘，即可得到矩形的最大面積。

時間複雜度：O(n)

空間複雜度：O(1)

看完之後是不是有了想法了呢，快來練練手吧>>