作者
標題 leetcode 姆咪姆咪
時間 Sat Nov 18 01:23:53 2023
標題 leetcode 姆咪姆咪
時間 Sat Nov 18 01:23:53 2023
https://i.imgur.com/pt05Jcx.png
![[圖]](https://i.imgur.com/pt05Jcxh.png)
這大概是我這輩子目前解過 最難的題目了
雖然基本上都是我同學在教我
謝謝同學
謝謝 謝謝喔
題目 找出一串陣列的最大矩形
然後 我其實根本沒想出解法
是他想到的
他的解法原理就是
先找到最小的數字他的矩形
再往左右找次小的矩形
比較他們的面積大小
然後透過遞迴不斷的找矩形
直到找到最大的
我只是
實現他的原理而已
我沒想到解法
不過還是花了我一整天來寫跟理解
我流淚了
int largestRectangleArea(int* heights, int heightsSize)
{
if(heightsSize == 0)
{
return 0;
}
if(heightsSize == 1)
{
return heights[0];
}
int min = heights[0];
int minp = 0;
int rmax = 0 ;
int lmax = 0 ;
int nmax = 0 ;
int ans = 0;
for(int i = 0 ; i < heightsSize ; i ++)
{
if(heights[i] < min)
{
min = heights[i];
minp = i;
}
}
int leftsize = minp ;
int rightsize = heightsSize - minp - 1 ;
int rp = minp ;
while(rp+1 < heightsSize && (heights[rp] == heights[rp+1] ))
{
rp ++;
rightsize --;
}
lmax = largestRectangleArea( heights, leftsize);
rmax = largestRectangleArea( heights+rp+1, rightsize);
nmax = heights[minp]*heightsSize;
if((nmax >= rmax) && (nmax >= lmax))
{
return nmax;
}
else if((lmax >= nmax) && (lmax >= rmax) )
{
return lmax;
}
else if((rmax >= nmax) && (rmax >= lmax))
{
return rmax;
}
return 0;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 134.208.57.64 (臺灣)
※ 作者: oin1104 2023-11-18 01:23:53
※ 文章代碼(AID): #1bLw6hrA (Marginalman)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1700241835.A.D4A.html
→ : 還好 我覺得找最大的環比較難搞1F 11/18 01:26
→ : 題目給我一下 我搞不好可以痛苦一個禮拜2F 11/18 01:26
→ : 你搜尋find largest ring應該就有了3F 11/18 01:27
推 : 你好厲害4F 11/18 01:29
→ : 不是我厲害 是我室友厲害
好 我看看
我沒看到最大的環那提欸5F 11/18 01:30
好 我看看
我沒看到最大的環那提欸5F 11/18 01:30
--